[Algorithm] 백준 1463, 이코테 1로 만들기 | 파이썬 (DP, Dynamic Programming)

※ 1463 1로 만들기

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

[문제]

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 이다.

 

ⓐ X가 5로 나누어 떨어지면 5로 나눈다.
ⓑ X가 3으로 나누어 떨어지면 3으로 나눈다.
ⓒ X가 2로 나누어 떨어지면 2로 나눈다.
ⓓ X에서 1을 뺀다.

 

정수가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다.

 

1. 26 - 1 = 25 ( ⓓ)

2. 25 / 5 = 5 ( ⓐ)

3. 5 / 5 = 1 ( ⓐ)

 

[입력 조건]

• 첫째 줄에 정수 X가 주어진다.(1 <= X <= 30,000)

[출력 조건]

• 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

[입력 예시]

26

[출력 예시]

3

 

문제 해결 TIP

다이나믹 프로그래밍 문제에서는 결과 저장용 리스트인 'DP테이블'을 먼저 만들어준다. 이때, dp[1]은 이미1이 되었으므로 0이다. 만약 X가 5라고 해보자. 2부터 X까지 반복문을 실행한다. dp[2] = dp[1]+1 = 1, dp[2] = min(dp[2],dp[1]+1) = 1 이렇듯 X가 2일 때는 1을 뺴는 법과 2로 나누는 법 2가지 경우를 만족할 수 있고 최솟값은 1이다. dp[3] = dp[2]+1 = 2, dp[3] = min(dp[3],dp[2]+1) = 2 따라서 2이다. dp[4] = dp[3] + 1 = 3, dp[5] = dp[4]+1 = 4, dp[5] = min(dp[5],dp[1]+1) = 1 따라서 1이다. 이렇게 반복문을 실행하며 메모이제이션 방식으로 실행하게 되는 것이다.

 

전체 코드

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)
    if i % 5 == 0:
        dp[i] = min(dp[i], dp[i // 5] + 1)
print(dp[X])