[ 파이썬(python) ] 백준 2231 - 분해합

📍 백준 2231 - 분해합

백준 2231 - 분해합

---

⚡️ 나의 풀이

언젠가 백준 단계별 문제풀이에서 이 문제를 봤었는데 그때는 이해가 안 돼서 그냥 넘겨버렸다. 이번엔 집중해서 문제를 잡았더니 풀 수 있었는데 시간 단축하는 방법은 끝내 찾지 못했다.

 

보통 브루트 포스의 문제의 범위는 1,000,000으로 주어지는 경우가 많다. 코딩테스트 볼 때 범위가 1,000,000이라면 브루트포스를 의심해보자!

 

총 3번에 걸쳐서 풀었고, 첫 번째는 시간 초과 (코드를 다시보니까 생성자가 없는 조건을 고려하지 않고 설계해서 시간초과가 났다. (21. 5. 13.)), 두번째는 정답판정이 났지만 실행시간이 많이 나왔다. 세 번째는 다른 사람의 코드 중 시간 최적화기능만 가져왔다.

 

1. 입력을 받는다.
2. target의 분해합을 구하기위해 해당 값을 str로 바꾸고 각 자리수를 모두 더해준 값을 temp에 넣어준다.
3. 현재 i값과 temp를 더한 값을 result로 초기화시킨다.
4. 만약 result 값이 target과 동일하다면? 해당 값은 생성자다.
5. 반복문을 모두 돌았는데도 생성자가 없다면 0을 출력한다. (for - else 구문)

 

이렇게 정답판정을 받았는데 1376 m/s이 걸렸다. 실행시간이 생각보다 길어서 최적화가 필요해 보였다. 반복문의 시작 범위를 줄이면 될 것 같은데, 어떻게 줄여야 할지 감이 오지 않았다.

 

시간 최적화하는 방법은 다음과 같다.

1. 분해합은 N과 N의 각 자릿수의 합이다.
2. 반대로, 생성자를 구하려면 분해합을 구하는 과정 중 N은 놔두고 N의 각 자릿수의 합만 빼주면 되는데, 어떤 수가 나올지 모르니까 각 자릿수에 나올 수 있는 최대 수(0~9)인 9를 빼주면 된다.
3. 그대로 적용하게 되면 N이 0~9가 나올때는 음수가 나온다. 따라서 절댓값(abs)을 씌워주자.

 

# 첫번째 시도: 시간 초과
target = int(input())
n, result = 0, 0

while target != result:
    n += 1
    temp = sum(map(int, str(n))) 
    result = n + temp
print(n)

# 두번째 시도: 성공
target = int(input())

for i in range(target):
    temp = sum(map(int, str(i)))
    result = i + temp
    if result == target:
        print(i)
        break
else:
    print(0)

# 다른사람의 코드: 시간 최적화
target = int(input())
min_target = abs(target - (len(str(target)) * 9))

for i in range(min_target, target):
    temp = sum(map(int, str(i)))
    result = i + temp
    if result == target:
        print(i)
        break
else:
    print(0)