티스토리 뷰

코딩테스트/백준

[백준/python] 2231번 - 분해합 / CLASS 2

sikaro 2023. 12. 12. 12:48
반응형
 

2231번: 분해합

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이

www.acmicpc.net

 

풀이

import sys
x=int(sys.stdin.readline().rstrip())
ans=[]
x1 = x
while (x):
    if x + sum(map(int,str(x))) == x1:
        ans.append(x)
    x-=1

if ans!=[]:
    print(min(ans))
else:
    print(0)

 

필자가 머리를 쥐어짜낸 풀이는 다음과 같다.

 

기본적인 원리는 자연수 n에서 계속 -1을 하며 x를 전부 대입해보며, 분해합인지 아닌지를 판별하는 것.

 

그러나 이 코드는 정말 안좋은 코드이다. 왜냐하면 map을 전체 범위에 대해 돌려야 하기 때문이다.

 

따라서 가장 좋은 코드는 범위를 줄여주는 게 가장 좋은 코드가 된다.

 

아래는 3위의 코드이다.

 

import sys
x=int(sys.stdin.readline().rstrip())
ans=[]
x1 = x
for i in range(max(0,(x-len(str(x1))*9)),x) :
    #(0,의 이유: x가 한자리수면 0 이하로 내려감)
    if x + sum(map(int,str(x))) == x1:
        ans.append(x)
    x-=1
if ans!=[]:
    print(min(ans))
else:
    print(0)

 

위의 코드와 비슷하지만, 범위를 제한해놓았다. 정확히는 x-len(str(x1))*9으로 정확히는 자신의 자릿수*9 만큼만 찾게 해놓았다.

무슨 뜻이냐면, 생성자의 범위는 각 자릿수마다 9씩 차이나는 범위가 최대이다. 즉, 1026면 은 최대 27차이인 999가 분해합이 되고, 10027면 최대 36차이인 9999까지만 생성자가 된다. 자릿수에 따라 범위가 다르므로 저렇게 범위를 제한해두면 대입 횟수를 획기적으로 줄일 수 있다.

 

따라서 저렇게 하면 속도면에서도 완벽한 코드가 완성된다.

반응형