[백준] 2231 분해합 python 알고리즘 문제

문제 2231. 분해합

 

1. 나의 코드와 발상 과정

n = int(input())

n_list = list(range(1,1000001))
for i in range(len(n_list)):
    m = 0
    struc = list(map(int, str(n_list[i])))
    m = n_list[i] + sum(struc)
    if m == n:
        print(n_list[i])
        break
if m != n:
    print(0)

 

처음에 이해를 잘 하지 못했는데 예제를 잘 들여다보면 금방 파악할 수 있다.

216을 입력 받으면 216을 '만들수 있는' 생성자 216 = '198'+1+9+8

을 찾아내라는 문제이다.

그럼 저건 어떻게 알 수 있을까 고민을 해보았는데,

배열을 두 개 만들면 되지 않나 하는 생각을 했다.

 

N이 100만개 주어지니까 for문 정도는 시간초과에 걸리지 않을 것 같아서

(1) n_list 라는 1 ~ 100만 까지의 배열을 생성하고,

(2) 그 배열의 각각의 원소를 struc 이라고 하는 리스트에 'int' -> 'str' -> 'int'화 과정을 통해 각각의 원소화를 하여 담았다.

(3) m을 이제 생성자와 그 생성자의 각 자리 합이라고 할 수 있다. sum(struc)이 생성자 뒤의 합을 의미한다.

(4) 그러면 이제 반복문을 돌리면서 n과 m이 일치하는지만 찾아주면 된다. i가 1부터 올라가기에 제일 빠른 놈이 출력될 것이다.

(5) 없으면 0을 출력한다.

 

 

2. 아쉬운 점

생각은 좋은데, 더 시간을 줄일 수 있는 코딩이 무엇이 있을까... 고민이 된다.