백준 / 1로 만들기 / 1463번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 1로 만들기 / 1463번 (실버 3단계)

문제 사이트: https://www.acmicpc.net/problem/1463

 

문제 설명

---

나의 풀이

# 다이나믹 프로그래밍
def solution(N):
    dp = [0] * (N + 1)

    # 초기 값으로 필수다
    if N >= 2:
        dp[2] = 1
    if N >= 3:
        dp[3] = 1

    # 나눴을 때 점화식에 존재하는 값을 가져와서 더해주면 된다.
    for i in range(4, N + 1):
        if i % 3 != 0 and i % 2 == 0:
            check = min(dp[i - 1], dp[i // 2])
            dp[i] = 1 + check
        elif i % 3 == 0 and i % 2 != 0:
            check = min(dp[i - 1], dp[i // 3])
            dp[i] = 1 + check
        elif i % 3 == 0 and i % 2 == 0:
            check = min(dp[i - 1], dp[i // 3], dp[i // 2])
            dp[i] = 1 + check
        else:
            check = dp[i - 1]
            dp[i] = 1 + check

    return dp[N]

n = int(input())

print(solution(n))

6은 2로 나눴을 때 dp[3], 3으로 나눴을 때 dp[2], -1했을 때 dp[5]가 존재 한다. 이 과정을 통해서 최소가 되는 값을 1과 더해서 새로운 값을 추가해서 점진적으로 나아간다.

---

※ 알아야 할 것

점화식을 세울 때 어떤 규칙을 가지고 있는 지 잘 확인해야 한다.

https://newkimjiwon.tistory.com/175

동적계획법(Dynamic Programming)