[백준 2231][파이썬] 분해 합

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

2231번: 분해합

 

1. 길이가 N+1이고 모든 값이 0인 리스트 생성 ( li [ i ]의 값은 i의 생성자가 됨 )

 

2. 반복문으로 1부터 N까지 3번 과정을 반복.

 

3. 분해 합을 구하고 리스트의 해당 인덱스 값이 0일 때만 그 값을 생성자로 변경

 

3번에서 값이 0일 때만 값을 생성자로 변경하는 이유는 반복문으로 1부터 증가하면서 분해 합의 생성자를 변경하기 때문에 가장 먼저 값이 변경된 값이 가장 작은 생성자가 된다.

 

그렇기 때문에 값이 이미 변경된 상태라면 그것이 곧 가장 작은 생성자, 즉 답이기 때문에 값이 변경된적 없었을 때만 바꾼다.