[BOJ] 백준 12852 1로 만들기 2 (Swift)

문제

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

12852번: 1로 만들기 2

풀이

다이나믹 프로그래밍을 사용해서 풀이할 수 있습니다.

X가 3으로 나누어 떨어진다면, [X / 3] + 1
X가 2로 나누어 떨어진다면, [X / 2] + 1
[X - 1] + 1 중에 가장 작은 값으로 갱신해주면 최솟값을 구할 수 있습니다.

그렇다면 만드는 방법에 포함되어있는 수는 어떻게 구할 수 있을까요?

저는 이전 정보를 기록할 Int 배열을 선언해주고,
prevNumber[i] = j : j를 사용해 i를 만듬
으로 정의해주었습니다.

최솟값을 갱신할 때, 갱신된다면 prevNumber도 갱신되도록 구현하였습니다.

그 이후, prevNumber[x]부터 1이 될 때 까지 반복해주었습니다.

소스코드

후기

다이나믹 프로그래밍 문제중에는 쉬운편이였습니다.
하지만 만드는 방법을 추적하는 것이 더 어려웠던 것 같습니다.

DFS를 사용해서도 추적이 가능할 것 같은데, 변수 하나를 더 선언하는 것이 편리해보여 이와같이 풀이했습니다.