백준 1463 1로만들기 파이썬

백준 1463 1로만들기 풀이

이 문제를 처음 마주했을 때는 단순히 입력받은 수를 if문의 나열을 통해
cnt를 1씩 증가시켜주는 방법으로 접근했습니다.
저와 마찬가지로 많은 사람들이 이러한 접근법을 생각해봤을 것이라 생각하고,
문제에서 주어진 10의 경우처럼, 2로 나누어지지만 -1을 해주고 난 후
1로 만들어주는 작업에 대해서 고민해야 합니다.

접근방식

1. 이 문제는 바텀업 방식으로 1부터 입력받은 수까지의 리스트를 활용해야 합니다.
2. 기본 전제는 dp의 원소가 모두 최소값이 저장된다는 것이고
3. 이 전제가 있다면 모든 dp[i]는 dp[i-1] 번째 + 1의 값을 가지게 됩니다.
4. 이러한 조건을 부여한 후, 2와 3으로 나누어지는 경우를 고려하면 n까지
5. 최솟값만 저장된 dp리스트를 만들 수 있습니다.

# 입력받기
import sys

input = lambda: sys.stdin.readline().rstrip()

n = int(input())

dp = [0] * (n+1)

for i in range(2, n+1):
    dp[i] = dp[i-1] + 1

    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)

    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i // 3] + 1)

print(dp[n])

해당 문제는 실버3레벨에 해당하지만, 단순히 이전의 dp리스트에 더하면서 점화식을

구하는 문제들과는 조금 달라 체감 난이도가 더 있었다고 생각합니다.

이 문제는 이전에 풀었던 2n타일링이나 다른 dp 문제들처럼 최솟값 혹은 최댓값만을 가지는

리스트를 참조하면서 빠르게 결과를 도출할 수 있도록 하는 특징을 지닙니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다.
Just do it & Keep steady