[백준 1463번] 1로 만들기(Python)

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

난이도 : 실버 3

1463번: 1로 만들기

 

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

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

입력

첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다.

출력

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

---

📌 풀이 접근 방법 

유명한 DP 문제

이 문제는 함수를 호출하는 최소횟수를 구하는 문제로 해석할 수 있다. 

 

1 에서부터 정수 X까지 만들어간다고 생각할 때, 각 숫자에서의 최소 연산 횟수를 저장해준다면, 

모든 숫자에 대해 /3 , /2, -1 을 하는 함수를 호출할 필요가 없이 이전에 계산했던 정보들을 그대로 가져다쓰면된다!! 

이게 DP의 핵심 아이디어 ! 

 

즉, dp 테이블에는 해당 숫자를 만드는데 최소 연산 횟수를 저장하게 될 것이다. 

 

예를 들어 N = 10이라고 가정해보자, 

1에서부터 10을 만들어가는 방향으로 dp 테이블을 채우면 다음과 같은 최소 연산 횟수가 나오게 될 것이다. 

 

 

 

이를 점화식으로 나타내면 다음과 같다. 

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

 

dp[i//2] +1, dp[i//3] + 1 은 2로 나누어 떨어지는 경우와 3으로 나누어 떨어지는 경우에 대해서만 고려해주면 된다. 

 

값을 그대로 가져다 쓰기 때문에 시간복잡도는 O(N)이 걸리게 된다.

따라서 N이 10^6이어도 제한 시간 안에는 문제를 해결할 수 있다. 

 

📌 정답 코드 

N = int(input())

dp = [0] * 10000001

#dp[i] : 숫자 i를 만드는데 필요한 최소 연산 횟수
#보텀업
for i in range (2, N+1) :
    dp[i] = dp[i-1] + 1 # 1을 빼주는 경우는 모든 숫자에 대해서 가능
    
    if i % 2 == 0: # 2로 나누어 떨어지는 경우, 최소값 갱신
        dp[i] = min(dp[i], dp[i//2] + 1) 
    
    if i % 3 == 0 :# 3으로 나누어 떨어지는 경우, 최소값 갱신
        dp[i] = min(dp[i], dp[i//3] + 1)

print(dp[N])