728x90
https://www.acmicpc.net/problem/2231
문제 요약 : 자연수 N의 분해합이 주어질 때, N의 가장 작은 생성자를 찾아라
M+ M의 각 자리수의 합 = N -> M을 N의 생성자라고 함
예를들어 245의 분해합은 256(= 245 + 2 + 4 + 5) 이므로 245는 256의 생성자
예제 입력1 :
216
예제 출력 1:
198
📌 풀이 )
1부터 N까지 반복하면서 각 숫자 i에 대해 분해합을 계산한다.
분해합과 i(원래 숫자)를 더하여 N과 같으면 i를 반환한다.
모든 숫자를 검사해도 생성자가 존재하지 않으면 0을 반환한다.
이 코드는 1부터 N까지 모든 수를 검사하기때문에 최악의 경우 시간복잡도는 O(N)이다. N의 최대값이 1000,000이므로 가능한 코드이다.
def result(N):
for i in range(1, N + 1):
digit_sum = sum(map(int, str(i)))
if i + digit_sum == N:
return i
return 0
N = int(input())
print(result(N))
'코테 공부 🔥' 카테고리의 다른 글
[프로그래머스/SQL] 부서별 평균 연봉 조회하기 (1) | 2024.05.28 |
---|---|
[백준/파이썬] 1436: 영화감독 숌 (1) | 2024.05.28 |
[백준/파이썬] 4153: 직각삼각형 (0) | 2024.05.27 |
[백준/파이썬] 2798: 블랙잭 (0) | 2024.05.27 |
[백준/파이썬] 1358: 하키 (0) | 2024.05.27 |
댓글