백준 1463

문제

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

코드

import sys

N = int(sys.stdin.readline())

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])

N = 1, 2, 3일 때의 값을 알기 때문에 DP 상향식으로 접근했다.

1을 빼는 연산이 연산 횟수를 최소화 하는 연산이라 가정하고 dp[i]에 dp[i - 1] + 1을 저장한다.

만약 i가 3으로 나누어 떨어지면,
1을 뺀 경우인 dp[i]의 값과 dp[i // 3] + 1의 값을 비교해서 더 작은 값을 dp[i]에 저장한다.

만약 i가 2로 나누어 떨어지면,
같은 과정을 반복한다.

이렇게 3단계를 거치고 나면, dp[i]의 최솟값을 구할 수 있다. 구하고자 하는 값은 dp[N]이므로 for문을 통해 N까지 반복한다.

기타

DP = Dynamic Programming = 동적 계획법
DP는 상향식과 하향식이 있다.

Greedy는 탐욕 알고리즘으로, 처음 생각한 최적의 방법이 반례 없이 끝까지 적용되는 경우에 쓴다.
Brute force는 모든 경우를 탐색한다.
그래서 DP는 Greedy와 Brute force의 중간에 위치한 알고리즘이라고 볼 수 있다.

참고 사이트:
https://jae04099.tistory.com/199

조건의 시간 제한이 0.15초인데, for문을 1번 돌리는 게 어떻게 시간 초과가 뜨지 않는지 잘 모르겠다..