[파이썬] 백준 2231번 분해합

문제 확인

2231번: 분해합

 

• 시간 제한 : 2초
• 메모리 제한 : 192MB

 

나의 풀이

• 시간 제한, 메모리 제한이 충분하다고 판단하여 분해합 미리 구해서 dict 구성했다.
• 이후 dict을 확인해서 N에 해당하는 분해합을 반환하는 방식으로 구현했다.
• 분해합을 미리 구해서 dict를 구성하면 메모리 낭비가 심함

# 분해합 저장
decompose_sum = {}
for i in range(1, 10**6 + 1):
    sum = i
    for j in str(i):
        sum += int(j)
    decompose_sum[i] = sum 

# 숫자 - 분해합 매칭
sum_num = {}
for k, v in decompose_sum.items():
    if v not in sum_num:
        sum_num[v] = k
        
n = int(input())
try:
    print(sum_num[n])
except:
    print(0)

 

다른 사람 풀이

• 숫자를 키우면서 분해합 확인
• map iterator에 바로 sum

n = int(input())  # 분해합을 입력값으로 받음

for i in range(1, n+1):   # 해당 분해합의 생성자 찾기
    num = sum((map(int, str(i))))  # i의 각 자릿수를 더함
    num_sum = i + num  # 분해합 = 생성자 + 각 자릿수의 합
    # i가 작은 수부터 차례로 들어가므로 처음으로 분해합과 입력값이 같을때가 가장 작은 생성자를 가짐
    if num_sum == n:
        print(i)
        break
    if i == n:  # 생성자 i와 입력값이 같다는 것은 생성자가 없다는 뜻
        print(0)

<알고리즘> 백준 2231번 분해합(파이썬)