[python] 백준 2231 : 분해합

반응형

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

2231번: 분해합

알고리즘 분류 : 브루트포스

 

---

분해합 : 어떤 수 N과 N의 각 자리수를 모두 더한 값의 합.

생성자 : 어떤 자연수 M의 분해합이 N인 경우, M을 N을 N의 생성자라 한다.

 

ex) 245 -> 245 + 2 + 4 + 5 = 256

245는 256의 생성자.

256은 245의 분해합.

 

자연수 N을 입력했을 때, N의 가장 작은 생성자를 구하는 프로그램을 작성하자.

 

 

접근 방법

1 : 1부터 입력한 값 N까지를 증가시키는 반복문을 돌리면서 각 숫자에 대한 분해합을 구한다.

 

2 : 구한 분해합이 입력한 숫자와 같다면 해당 분해합 값은 입력한 숫자의 생성자이므로 반복문을 빠져나와 그 값을 출력한다.

 

3 : 만약 반복문이 끝날때까지 입력한 값과 같은 값이 존재하지 않는 경우, 입력한 숫자에 대한 생성자가 존재하지 않는 것이므로 0을 출력하도록 한다.

 

 

정답 코드

N = int(input())
x = 0
for i in range(N):
    a = list(map(int, str(i)))
    if N == sum(a) + i:
        x = i
        break;
print(x)

 

코드 풀이

 

1 : 1부터 입력한 값 N까지를 증가시키는 반복문을 돌리면서 각 숫자에 대한 분해합을 구한다.

N = int(input())
x = 0
for i in range(N):

입력받은 정수에 대한 접근을 하기위해 입력받은 문자열을 먼저 정수로 형변환 시킨다.

 

 

가능한 모든 경우의 수를 찾는 브루트포스 알고리즘을 활용한다. 1부터 시작해서 가장 작은 생성자 값을 찾아내면 바로 반복문을 탈출하는 방식이지만 알고리즘 특성상 많은 시간이 걸린다.

 

 

245를 입력받았다면 245 -> 245 + 2 + 4 + 5 = 256

이처럼 생성자를 구하기 위해서는 해당 숫자와 해당 숫자의 각 자릿수를 모두 더한 값을 구해야 한다.

문자열을 입력받고 이를 원소로 하는 리스트를 생성하면 문자 단위로 나눌 수 있다.

 

a = "pingpong"
print(list(a))

['p', 'i', 'n', 'g', 'p', 'o', 'n', 'g']

 

문제와 같이 입력받은 숫자를 각 자릿수마다 구분해서 리스트에 담아보려 하였다.

N = int(input())
print(list(N))

>> 245
Traceback (most recent call last):
TypeError: 'int' object is not iterable

 

iterable은 단일 객체가 아닌 반복할 수 있는 문자열, 튜플, 딕셔너리, range() 함수 등을 의미한다. 정수 자체로는 각 자릿수에 대한 인덱스 값을 할당할 수 없기 때문에 pingpong문자열을 리스트 형태의 ['p', 'i', 'n', 'g', 'p', 'o', 'n', 'g']으로 나눠받는 것과 같은 방법으로는 접근할 수 없다.

 

N = int(input())
x = 0
for i in range(N):
    a = list(map(int, str(i)))
    if N == sum(a) + i:
        x = i
        break;
print(x)

 

정수의 각 자릿수를 리스트로 받기 위해서는 map()함수를 활용해야 한다.

문자열은 iterable에 해당하므로 1~입력받은 값(정수로 변환한) N까지의 값에 해당하는 i를 str으로 형변환하여 받고, 다시 map()함수로 각 자릿수 값을 int로 형변환한다.

이렇게하면 N에 245를 입력받았을 때 리스트 a에 [2, 4, 5]를 담을 수 있다.

 

 

2 : 구한 분해합이 입력한 숫자와 같다면 해당 분해합 값은 입력한 숫자의 생성자이므로 반복문을 빠져나와 그 값을 출력한다.

 

sum함수는 리스트의 모든 원소를 더한 값을 반환한다. 여기에 i를 더하면 i의 분해합이 된다.

이 값이 입력한 값 N과 같다면 N의 생성자와 같은 값이므로 반복문을 탈출하여 그 값을 출력하도록 한다.

 

 

 

3 : 만약 반복문이 끝날때까지 입력한 값과 같은 값이 존재하지 않는 경우, 입력한 숫자에 대한 생성자가 존재하지 않는 것이므로 0을 출력하도록 한다.

 

만약 반복문을 중간에 탈출하지 못하면 생성자를 찾지 못한 것이므로 처음에 선언한 x = 0 값 그대로 출력하도록 한다.