백준 #2231 분해합

explorer999 2023. 8. 31. 11:21

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

예제 입력 1 복사

예제 출력 1 복사

내 풀이:

n=int(input())

b=0

for i in range(n):

arr=list(map(int, str(i)))

a=0

for j in arr:

a+=j

if a+int(i)==n:

print(int(i))

b+=1

break

if b==0:

print('0')

0부터 n까지의 자연수에 대하여,,

각 자릿수를 원소로 하는 리스트로 만든다. 초기값 0인 a에다가 각자릿수를 하나씩 더하는 게 안쪽 for문의 내용이고, for문이 끝나면 각 자릿수의 합a에다가 그냥 i라는 숫자 그대로를 더해서 그게 n이랑 같다면 출력하고 b에 1 더하고 바깥쪽 for문에서 벗어나기.

만약 b가 0이면(한번도 생성자 출력 안했으면) 0을 출력한다.

쉽다고 생각하고 풀었다가 생성자 없는 경우 조건을 안 봐서 틀렸다. 문제는 잘 읽자

다른 사람들보다 출력시간?이 개오래걸리는데 이유를 알아보자.

n = int(input())

for i in range(1, n+1):

num = sum((map(int, str(i))))

num_sum = i + num

if num_sum == n:

print(i)

break

if i == n:

print(0)

쪼끔 더 빨리 돌아가는 다른 사람의 풀이

num = sum((map(int, str(i))))

num_sum = i + num

이부분 때문에 쓸데없이 n을 리스트로 재정의하지도 않고, 원소 다 더하는데 for문 하나 더 쓰지도 않았다. 생성자가 없는 경우가 i==n인 경우라고 한 것도 다름.

N = input()

a= int(N) - 9*len(N)

b = int(N)

if a < 0:

a = 0

for i in range(a,b):

total = i + sum(map(int,str(i)))

if total == int(N):

print(i)

break

if i == b-1:

print(0)

다른 사람이 푼 엄청 빨리 출력되는 풀이

일단 생성자는 a와 b사이에 있다고 먼저 설정함. a는 n에서 자릿수만큼 9를 뺀 값이고, b는 그냥 int(n)이다.

그래서 a와 b사이에서 조건을 만족하는 생성자가 나오면 그 값을 프린트한 후 바로 for문 종료(최솟값 구하는 거니까)

만약 a부터 b-1까지 다 돌았는데 생성자가 안 나왔으면 i=b-1일 것이다. 그러면 그냥 0을 출력함.

#chat gpt가 알려준 차이점

내 코드:

0부터 n까지의 모든 수에 대해 조건을 검사하고 조건을 만족하는 값을 찾아내기

0부터 n까지 모든 수에 대해 반복문을 돌리고 각 수마다 자릿수를 분리하고 더하는 작업 등 복잡한 연산을 수행

반복문 안에서 다른 조건문을 사용하여 조건을 만족하는 값을 찾으면 바로 반복문을 종료하고 출력하는데,

이는 검사해야 하는 모든 수에 대해 조건을 검사하는 작업을 줄여주기 때문에 조금 더 최적화된 코드 구조?

마지막 코드:

주어진 조건을 만족하는 값을 찾아내기

입력 값 n에 대해서 범위를 제한하여 반복문을 돌림

각 숫자에 대해 연산을 수행하는 데 필요한 작업이 상대적으로 적음