[백준 10단계] 2231 분해합

🥕 [ 백준 2231 ] 분해합

문제 링크

url : https://www.acmicpc.net/problem/2231

2231번: 분해합

 

🍒 문제 분석

자연수  N을 M + M의 각 자리 수로 표현할 수 있을 때, M을 N의 생성자라고 한다.

생성자는 여러 개 일수도 있고, 1개일 수도 있으며, 아예 없을 수도 있다.

생성자들 가운데 가장 작은 수를 구하여라

가령 256 을 넣으면 198 이 출력된다.

생성자가 없을 경우에는 0을 출력하기로 한다.

 

🥑 코드

N = int(input())
l = []
for M in range(1,N+1):
    H=M+sum(map(int, [i for i in str(M)]))
    if H == N:
        print(M)
        break
else: print(0)

 

🍓 내 해결 과정

HS님 코드를 많이 참고했다.

 

처음에 내가 제출한 코드는 다음과 같았다. ( 틀린 코드 )

def find_m(N):
    if N < 10 :
        return N
    M = N - 9*(len(str(N))-1) - 1
    H = -1
    while N != H:
        M += 1
        if N == M:
            return 0
        H = M
        str(M)
        for i in str(M):
            H += int(i)
    return M

N = int(input())
print(find_m(N))

 

최대한 반족 횟수를 줄이기 위해

입력 값 N에서 (N의 자릿수 -1) * 9 를 뺀 값을 start라고 하면, 적어도 생성자는 start 이상이지 않을까라고 생각해 이를 구현하였다.

 

그러나 N이 1의 자리일 때, 값이 이상하게 나와 예외처리를 해주어야했고,

예외 처리를 이상 하여 답이 틀리게 나왔고, 나는 이상한 점을 깨닫지 못했었다.

 

HS 님 코드를 보고 최대한 코드를 보기 좋게 다시 썼고,

문제 테마가 브루트 포스인 점을 생각해서 그냥 N이 1부터 돌리는 것으로 바꿨다.

 

그러자 더 이상 예외 처리 관련해서 문제가 발생하지 않았고, 코드도 보기 편해졌다.

 

시간 제한이 2초이며, N은 1000000 까지 주어졌었다.

대충 1초 당 1억 정도의 연산이 가능하다고 한다. 백만가지의 N이면, 대충 빅 오 N 제곱만 아니면, 빅 오 N 정도는 얼마든지 가능한 것이다.

 

🍉 깨달은 점 및 정리

 

1.  sum(map(int, [i for i in str(M)]))

숫자의 각 자리수를 더하는 연산을 할 때 다음의 식을 쓰면 매우 깔끔하다.

나는 이 코드를 어쩔 때는 생각나서 쓰고, 어떨 때는 생각이 나지 않아 못쓰는데, 이는 연습량으로 해결할 문제라 생각된다.

 

2. 틀리면 보통은 예외처리에서 잘못된 것이다.

( 예외처리를 잘못 해줬거나, 또는 예외 처리를 안해줬거나 )

만약 브루트 포스로 접근할 수 있는 문제면, 그냥 전수 조사 돌려서

예외사항이 안나오겠끔 하는 것도 좋은 접근 방법인 것 같다.