2231번: 분해 합
문제)
어떤 자연수 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
f_num = int(input())
num = f_num
count = 1
a= True
while a: #입력값의 자릿수 구하는 방법
if num / 10 >= 1:
num = num / 10
count += 1
elif num / 10 < 1:
a = False
minus = count * 9 #자릿수마다 나올 수 있는 최대 수는 9
min_create = f_num - minus #생성자가 존재할 수 있는 가장 작은 값.
while True:
sub = str(min_create)
sub = list(map(int, sub)) #숫자를 리스트로 만들 것.
digit_num = 0
for i in sub:
digit_num += i # 각 자리 수를 더한 값 digit_num에 담는다.
if min_create + digit_num == f_num: #생성자인지 체크.
print(min_create)
break
else:
min_create += 1 #생성자가 아닐 경우 1을 더하고 다시 반복
|
cs |
처음 짰던 알고리즘이다. IDE로 실행 했을경우 답은 맞지만, 채점에서는 시간초과로 틀렸다고 나온다.
이를 해결하기 위해 의미 없이 반복하는 while문을 최대한 없애야겠다고 생각해서 개선 해봤다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
def test(a):
sub = str(a)
sub = list(map(int, sub))
digit_num = 0
for i in sub:
digit_num += i
if a + digit_num == f_num: #생성자인지 체크.
print(a)
else:
a += 1
test(a)
f_num = int(input())
num = f_num
nums = str(f_num)
nums = list(map(int, nums))
count = len(nums) #입력 값의 자릿수 구하기
minus = count * 9 #자릿수마다 나올 수 있는 최대 수는 9
min_create = f_num - minus #생성자가 존재할 수 있는 가장 작은 값.
test(min_create)
|
cs |
재귀함수를 이용한 방법을 생각해보았으나, 이 경우 제출했을 때
런타임 에러 (RecursionError)가 발생했다. 찾아보니 python 이 정한 최대 재귀 깊이보다 깊을 경우
이러한 에러가 발생한다고 한다. 이 방법도 실패... 사실 while문과 큰 차이는 없는 방법이었다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
def test(a): #생성자가 맞는지 확인하는 함수.
sub = str(a)
sub = list(map(int, sub))
digit_num = 0
for i in sub:
digit_num += i
if a + digit_num == f_num: #생성자인지 체크.
answer.append(a)
f_num = int(input())
num = f_num
answer = []
nums = str(f_num)
nums = list(map(int, nums))
count = len(nums) #입력 값의 자릿수 구하기
minus = count * 9 #자릿수마다 나올 수 있는 최대 수는 9
min_create = f_num - minus #생성자가 존재할 수 있는 가장 작은 값.
for i in range(0, minus + 1):
min_create += 1
test(min_create)
print(answer[0])
|
cs |
나름대로 최대한 짱구를 굴려서 만들어낸 알고리즘이다. 문제는 이젠 시간초과가 아닌 value, index에러가 뜬다는 것.
더 이상 더 깊은 심연의 늪으로 떨어지기 싫었던 나는 결국 다른 분의 풀이를 보았다.
거기서 숫자로 이루어진 list를 더하는 새로운 함수도 발견했다.
|
1
2
3
4
5
6
7
8
9
10
|
num = int(input())
result = 0
for i in range(1, num+1):
A = list(map(int, str(i)))
result = i + sum(A)
if result == num:
print(i)
break
elif i == num:
print("0")
|
cs |
솔직히 하나하나 1부터 시작할 줄은 몰랐다. 시간제한이 2초인데다가, N의 최대범위는 1,000,000이었기 때문.
정공법이 더 간단한 경우가 많다는 생각이 들었다. 크게 돌지말고 직진으로 가자
출처 : https://www.acmicpc.net/problem/2231
2231번: 분해합
어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이
www.acmicpc.net
'Develop > 백준 (python)' 카테고리의 다른 글
| [백준] 2775번: 부녀회장이 될테야 (python) (0) | 2022.01.12 |
|---|---|
| [백준] 2292번: 벌집 (python) (0) | 2022.01.12 |
| [백준] 1259번: 팰린드롬수 (python) (0) | 2022.01.11 |
| [백준] 1085번: 직사각형에서 탈출 (python) (0) | 2022.01.10 |
| [백준] 11720번: 숫자의 합 (python) (0) | 2022.01.09 |
