[백준] 1463 1로 만들기 (파이썬 python)

 

 

문제 링크

 

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

1463번: 1로 만들기

 

 

문제 설명

 

 

 

 

문제 풀이

 

 

Dynamic Programming 문제이다.

dp 테이블에 모든 원소를 0으로 초기화시켜준 후 하나씩 반복하여 계산을 하는 것이다.

DP는 처음에는 이해가 잘 안되는데 생각해보면 간단하다.

 

예를 들어 4에 대한 연산의 결과를 생각해보자.

4는 4 -> 2 -> 1 의 연산을 하게된다.

그런데 이걸 하나씩 매번 해줄 필요가 없다.

2에 대한 연산의 횟수(DP(2))에 2를 도출해낸 연산(나누기 2) 한 번(+1)을 카운트해주면

DP[4] = DP[2] + 1이 된다.

이와 같은 방식으로 코드를 작성하면 된다.

 

최소 횟수로 연산을 완성시켜야 하므로 최솟값을 구하는 연산이 필요하게 된다.

-1을 하는 연산을 작성하고 2로 나누어지는 경우와 3으로 나누어지는 경우를 if문으로 구현하여

그 중에서 횟수의 최솟값을 구하면 된다.

 

x = int(input())

dp = [0] * (x + 1)

for i in range(2, x + 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[x])