[백준] 1463 1로 만들기 (실버3) / DP, DP풀이법 정리

문제요약

나의 코드 및 설명

n = int(input())

dp = [0] * (n+1)

for i in range(2, n+1):
    dp[i] = dp[i-1] + 1 # 1로 더하는 경우 (dp[i-1] + 1) -> dp의 값에는 최소값이 저장되기 때문에 가
    if i % 2 == 0: #2로 나누어 떨어지는 경우
        dp[i] = min(dp[i], dp[i//2] + 1) #dp[i//2]에 저장된 값+1 과 dp[i](1로 더하는 경우) 비교
    if i % 3 == 0: #3으로 나누어 떨어지는 경우
        dp[i] = min(dp[i], dp[i//3] + 1) #dp[i//3]에 저장된 값+1 과 dp[i](1로 더하는 경우) 비교

print(dp[n])

피드백

DFS, BFS, 백트래킹에 이어 DP 연습을 위해 풀어본 문제. 먼저, 손으로 그려서 규칙을 찾고 DP 테이블을 그려서 어떻게 코드로 구현할 지 고민하는 것이 DP 문제풀이의 핵심이다. 어려운 문제일수록 규칙을 찾는 것이 힘들고, 점화식을 만드는 것이 힘들다고 한다. 앞으로 꾸준한 연습을 통해 DP 알고리즘에 익숙해질 수 있도록 학습해야겠다.