백준 12852. 1로 만들기 2

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

12852번: 1로 만들기 2

 

이 문제는 나눠지는지 확인하고 나눠봐도 되지만 1부터 시작해서 더하거나 2, 3을 곱하면서 계산해도 된다.

 

1 기준 

1+1=2 이므로 d[2] = min(INF, d[1]+1) = 1

1*2=2 이므로 d[2] = min(1, d[1]+1) = 1

1*3=3 이므로 d[3] = min(INF, d[1]+1) = 1

 

2 기준 

2+1=3 이므로 d[3] = min(INF, d[2]+1) = 2

2*2=4 이므로 d[4] = min(INF, d[2]+1) = 2

2*3=6 이므로 d[6] = min(INF, d[2]+1) = 2 

...

 

N을 1로 만드는 방법에 포함되는 수의 출력은, d 배열을 pair로 만들어서 최솟값을 저장할때마다 이전 숫자도 저장해줘서, 거슬러 올라가면서 출력해줬다.