문제
접근
DP를 이용하는 문제이다.
바텀업 방식으로 풀었다.
N에서 1로 만드는 방법이지만, 1부터 N까지 타고 올라갔다.
dp[1]은 0으로 시작하고, n까지 올라가며 dp[i] = dp[i-1] + 1을 해준다.
이러면 1을 빼는 연산에 대해서 처리해준 것이다.
그리고 i가 3으로 나눠지거나 2로 나눠진다면 추가적으로 연산을 진행한다.
예를 들어 3으로 나누어진다면, dp[i] = dp[i//3] + 1이 될 것이다.
현재 dp에는 1을 뺴는 연산의 결과가 담겨있다.
그렇다면 min(dp[i], dp[i//3] + 1)을 통해 둘 중에 더 작은 값을 이용하면 된다.
이렇게 거꾸로 n까지 올라가면 dp[n]에는 1에서 n으로 오는 최단 경로의 연산 횟수가 담겨있다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
n = int(input())
dp = [0] * (n+1)
for i in range(2, n+1):
dp[i] = dp[i-1] + 1
if i % 3 == 0:
dp[i] = min(dp[i], dp[i//3]+1)
if i % 2 == 0:
dp[i] = min(dp[i], dp[i//2]+1)
print(dp[n])