728x90
https://www.acmicpc.net/problem/2231
2231번: 분해합
어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이
www.acmicpc.net
1. 길이가 N+1이고 모든 값이 0인 리스트 생성 ( li [ i ]의 값은 i의 생성자가 됨 )
2. 반복문으로 1부터 N까지 3번 과정을 반복.
3. 분해 합을 구하고 리스트의 해당 인덱스 값이 0일 때만 그 값을 생성자로 변경
3번에서 값이 0일 때만 값을 생성자로 변경하는 이유는 반복문으로 1부터 증가하면서 분해 합의 생성자를 변경하기 때문에 가장 먼저 값이 변경된 값이 가장 작은 생성자가 된다.
그렇기 때문에 값이 이미 변경된 상태라면 그것이 곧 가장 작은 생성자, 즉 답이기 때문에 값이 변경된적 없었을 때만 바꾼다.
728x90
'백준 알고리즘' 카테고리의 다른 글
| [백준 11659] 구간 합 구하기 (0) | 2023.02.15 |
|---|---|
| [백준 3053][파이썬] 택시 기하학 (0) | 2023.02.13 |
| [백준 25682][파이썬] 체스판 다시 칠하기 (0) | 2023.01.28 |
| [백준 9020][파이썬] 골드바흐의 추측 소수 판별 (에라토스테네스의 체) (0) | 2023.01.26 |
| [백준 2563][파이썬] 색종이. 이차원 배열 (0) | 2023.01.25 |