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

문제

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

1463번: 1로 만들기

풀이

이 문제는 1을 다른 해당 숫자로 만드는 방법의 최소 연산의 수를 구하는 것으로도 생각할 수 있습니다.

1은 1이니깐 0이고,
2는 1에서 1을 더해서 만들 수도 있고, 2를 곱해서도 만들 수 있으므로 최소 연산의 수는 1이고,
3은 1에서 1을 두번 더하는 방법과 3을 곱해서 만들 수 있습니다.

1을 두번 더하는 방법은 연산의 횟수가 2이기 때문에 3을 곱해서 만드는 연산을 1번 사용하는 것이 최소 연산의 수 일 것입니다.

4도 1에서 1을 세번 더하는 방법, 2에서 2를 곱하는 방법으로 나뉘게 됩니다.
2를 만드는 최소 연산의 수는 1이고, 2에서 4를 만드는 최소 연산의 수도 1이므로 총 최소 연산의 횟수는 2가 됩니다.

이런식으로 1부터 차근차근 늘려서 최소 연산의 횟수를 구할 수 있습니다.

정의 : $f(n)$ = 1에서 n으로 만드는데 드는 최소 연산의 수
초기값 : $f(1) = 0$
점화식
$if \ \ \ \ n \mod 3 == 0 \ \ \ \ f(n) = min(f(n), f(n/3) + 1)$
$if \ \ \ \ n \mod 2 == 0 \ \ \ \ f(n) = min(f(n), f(n/2) + 1)$
$f(n) = min(f(n), f(n - 1)+1)$

소스코드

후기

dp 문제 치고 쉬웠던 문제였습니다.
n에서 1로만드는 것이 아닌 1에서 n으로 만든다고 생각해서 풀이를 떠올릴 수 있었습니다.