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

사용 언어: Python 파이썬

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

1463번: 1로 만들기

이 문제는 Dynamic Programming을 사용해서 풀 수 있다.

 

Dynamic Programming이란?

Dynamic Programming(동적 계획법)은 주어진 문제를 잘게 나누어서 하위 문제들을 푼 후, 각 답을 이용하여 주어진 문제를 푸는 방식이다. DP를 풀 때 생각해야하는 것은 딱 하나다. 바로 '점화식'이다. 점화식만 세우면 문제 풀이는 끝났다.

 

주어진 문제를 읽어보자.

 

정수 X로 할 수 있는 연산은 총 3가지이다.

1. X를 3으로 나누기

2. X를 2로 나누기

3. 1 빼기

 

주어진 연산을 반복하여 X를 1로 만들 수 있는 최솟값을 출력하면 된다.

 

각 연산에 대해 좀 더 깊게 알아보자

1. X가 3으로 나누어 떨어진다면? dp[n] = dp[n/3] + 1

2. X가 2로 나누어 떨어진다면? dp[n] = dp[n/2] + 1

3. 1을 뺄 경우? dp[n] = dp[n-1] + 1

 

잘 이해가 안된다면, X에 숫자를 직접 넣어서 생각해보자.

X를 6이라고 가정하자.

 

1. 6은 3으로 나누어 떨어지므로 dp[6] = dp[2] + 1 (2에서 3을 곱하면 6이된다. 즉 dp[2]에서 3을 곱하는 연산을 한 번 더 하면 6을 만들 수 있다.)

2 .6은 2으로 나누어 떨어지므로 dp[6] = dp[3] + 1 (3에서 2을 곱하면 6이된다. 즉 dp[3]에서 2를 곱하는 연산을 한 번 더 하면 6을 만들 수 있다.) 

3. 6에서 1을 빼면 5가 되므로 dp[6] = dp[5] + 1(5에서 1을 더하면 6이 된다. 즉 dp[5]에서 1을 더하는 연산을 한 번 더 하면 6을 만들 수 있다.)

 

이 3가지 방법 중에서, 가장 연산 횟수가 적은 경우의 수를 찾아야한다. 따라서 구하고자하는 점화식은 다음과 같다.

dp[n] = min(dp[n/3] +1, dp[n/2] + 1, dp[n-1] + 1) = min(dp[n/3], dp[n/2], dp[n-1]) + 1

dp[i] = i를 1로 만들 수 있는 연산의 최솟값

 

이를 코드로 옮겨보자

 

case = int(input())

dp = [0,0,1,1]

# dp[n] = min(dp[n-1] , dp[n//2], dp[n//3) + 1
for i in range(4, case+1):
    dp.append(dp[i-1]+1)
    if i%2 == 0:
        dp[i] = min(dp[i//2]+1, dp[i])
    if i%3 == 0:
        dp[i] = min(dp[i//3]+1, dp[i])

print(dp[case])