[BOJ][Python][브2][2231] 분해합

문제 링크

문제링크

첫 번째 풀이

정답코드

import sys
from math import pi, sqrt
from collections import deque

# sys.stdin = open("input.txt", 'r')

n = int(input())
arr = []
ans = 0
for i in range(max(1, n-54), n):
    x = i
    x += sum(map(int, str(i)))
    if x == n:
        ans = i
        break
print(ans)

두 번째 풀이 : 빠른 풀이

정답코드

n이 1,000,000일 때 100 ~ 10000 근처에서 생성자를 구할 가능성은 없기 때문에, 최대한 가능성이 있는 범위에서만 확인을 하면 풀이시간을 단축할 수 있습니다.

1,000,000이 n으로 들어왔다고 했을 때, n의 가장 작은 생성자가 x라고 하겠습니다. x는 6자리 수일 것이고 따라서 x + 9(자릿수 최대값) * 6(x의 최대 자릿수 갯수) = 1,000,000일 것입니다.

n이 100일 때는 x + 2 * 9 == 100일 것이기 때문에 x의 범위는 [100-92,100]정도가 될 것입니다.

n이 작을 때에도 6 * 9를 빼는 것은 시간이 약간 늘어나는 것뿐이기 때문에 6 * len(n)을 빼지 않고 54를 빼기도 합니다.

import sys
from math import pi, sqrt
from collections import deque

# sys.stdin = open("input.txt", 'r')

n = int(input())
arr = []
ans = 0
for i in range(max(1, n-54), n):
    x = i
    x += sum(map(int, str(i)))
    if x == n:
        ans = i
        break
print(ans)

Success Notice: 수고하셨습니다.