[파이썬] 2231번: 분해합

2231번: 분해합 (acmicpc.net)

2231번: 분해합

 

첫 풀이

n = int(input())
sums = []

for num in range(1, n + 1):
    sum = num
    s = str(num)
    for j in s:
        sum += int(j)
    	if sum == n:
        	sums.append(num)

if len(sums) == 0:
    print(0)
else:
    print(min(sums))

 

처음엔 이렇게 했는데 계속 틀렸다고 나와서 질문게시판을 보며 반례를 찾았다.

로직은 맞았지만 두 번째 for문의 if문에서 들여쓰기를 잘못한 것이 문제였다.

입력이 31일 경우 원래대로라면 0이 나와야 하지만, 위 코드에서는 num=29에서 첫째자리인 2만 더했는데도 생성자로 분류되어 29가 출력된다.

 

최종 풀이

n = int(input())
sums = []

for num in range(1, n + 1):
    sum = num
    s = str(num)
    for j in s:
        sum += int(j)
    if sum == n:
        sums.append(num)

if len(sums) == 0:
    print(0)
else:
    print(min(sums))

if문의 들여쓰기를 한 칸 빼내어 다시 돌려보면 바르게 출력된다. 

 

 

다른 사람의 코드

n = int(input())
result = 0
for i in range(1,n):
    lst = list(map(int,str(i)))

    result = i+sum(lst)
    if result ==n:
        print(i)
        break;
    if i==n:
        print(0)

map을 이용해 각 자릿수를 분리하여 숫자로 바꾼 후 리스트에 저장한다.

sum()을 이용하여 자릿수의 합을 한번에 구한다.

이렇게 하면 for문을 한 번만 돌기 때문에 시간복잡도가 O(n)으로 줄어들어 훨씬 빨라진다.