백준 2231번 풀이

문제

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

2231번: 분해합

어떤 수의 생성자를 구하는 문제. 자세한건 후술.

 

Reference

https://yongku.tistory.com/787

백준 2231번 분해합 파이썬(Python)

 

풀이

일단 생성자가 뭔지를 알아야 이 문제를 풀 수 있다. 분해합은 어떤 수와 그 자릿수를 더하는 것으로, 예를 들자면

255 + 2 + 5 + 5 = 267

이런 식으로 더하는 것. 이 때, 255는 267의 생성자이다. 이런 식으로 어떤 수와 그 수의 자릿수를 다 더했을 때 입력한 수가 되면 그게 생성자이다. 그럼 ‘제일 작은 생성자’가 뭔지는 알 것 같은데, 생성자가 없는 수도 있나요? 1이랑 255 없었음.

import sys
a = int(sys.stdin.readline().strip())
sum = 0
for i in range(1,a+1):
    print(i)

sum은 나중가면 다른걸로 바꾼다. 배열 합이 그래서… 아무튼 일단 입력받은 수까지 for문 뺑뺑이를 돌려보자.

import sys
a = int(sys.stdin.readline().strip())
result = 0
for i in range(1,a+1):
    A = list(map(int, str(i)))
    result = sum(A) + i
    if result == a:
        print(i)
        break
    elif i == a:
        print(0)

이게 답인데… 숫자를 배열하해서 각각의 자리수를 리스트에 넣고 그 리스트의 합(sum)을 구해 원래 수와 더하게 된다. 그걸 한땀한땀 정성스럽게 계산하다가 생성자가 나오면 출력하고 땡이고, 계산 다 해봤는데 i가 입력한 수까지 가게 되면 씁 이건 에반데가 된다. 그러면 여기서 여러분들은 한가지 궁금증이 생기게 된다.

 

그런데 break가 굳이 있어야 할 이유가 있나요? 사족 아니예요? 

 

문제에 이런 얘기가 있었다.

 

물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

그리고 생성자가 ‘없는’ 경우를 elif에서 처리했고, ‘가장 작은 생성자’에 대한 처리를 break로 했다고 보면 된다.

1024 # 입력한 값
998
1016

1024는 생성자가 두 개거든. 이런 경우 응애 애기출력초과! 가 여러분을 반길 수 있다.

import sys
a = int(sys.stdin.readline().strip())
result = 0
i = 1

while i <= a:
    A = list(map(int, str(i)))
    result = sum(A) + i
    if result == a:
        print(i)
        break
    elif i == a:
        print(0)
    i += 1

이건 While버전. for문은 1부터 입력값+1이고, while은 i가 입력값과 같아질때까지 계속 한다. if문에 break가 들어가는 건 똑같다.