곧죽어도 콛잉

https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 이번 문제는 그냥 dp하나만 보면 간단하게 풀릴 수 있었는데 .. 최소값을 구하는 것 뿐만 아니라 최솟값이 나오기까지의 과정도 보여줘야한다. 즉, dp 진행 중, 중간의 값들을 계속해서 "Tracing" 해야한다. 다행스럽게도, 잘 생각해보면 특정값 X는 최소의 연산횟수를 보장하는 경로가 단 한가지 연산 밖에 없다. (여러 경로가 있지만, 그럼에도 최선의 선택은 1개뿐.) 예를 들어, 10의 경우는 9, 9의 경우는 3, 3의 경우는 1이 전부다. 10 9 3 1 즉 이것을 새로운 DP의 값으로 보여줄..