백준 1463번 파이썬 문제풀이(DP - 1로 만들기)

---

코드

X = int(input())
dp = [0] * (X + 1)  # 각 인덱스(1~X)마다 1을 만들기위한 연산 횟수를 저장할 DP배열 선언, 
# d[1] = 0 인이유는 1일때는 연산 횟수가 0이기 때문이다.

# 2일때부터 n번째 일때까지 몇번을 시행해야하는지 체크
for i in range(2, X + 1):

    # -1 했을 때의 횟수 저장
    dp[i] = dp[i - 1] + 1  # 일단 처음에 그 전에 시행했던 횟수(d[i-1])에서 +1 만해주면 되기 때문에 d[i] = 전의횟수(d[i-1]) + 1

    # 3으로 나눴을 때의 횟수저장
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i // 3] + 1)  # 만약 3으로 나누어 진다면 6은 2일때의 횟수에서 + 1 만 하면 되기 때문에

    # 2로 나눳을 때의 횟수저장
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i // 2] + 1)  # 만약 2로 나누어진다면 4는 2일때의 횟수에서 + 1 만 하면 되기 때문에

print(dp[X])  # 해당 X번째의 횟수 출력

-> 위 문제는 DP의 아주 기본적인 문제라고 할 수 있다. 이 문제를 처음 DP를 모르고 풀 때는 입력받은 X값에서 자꾸 1로 내려갈라고 생각을 했다. 그러니 자꾸 시간초과가 발생했다. 위 문제는 반대로 1부터 입력받은 X까지 횟수를 올려가며 저장을 해야하는 문제이다. 위의 코드에서 자세한 설명을 해놨으니 주석을 보면 쉽게 이해할 수 있다고 생각한다.