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

문제

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

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

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

 

기록

(dp 3일차) greedy로 자연스럽게 풀었다가 한 번 틀리고 dp로 풀었다. 당연히 위의 순서대로 우선순위로 정해서 계산해나가는게 최적해일 줄 알고 greedy로 했는데 10 같은 경우는 아니었다ㅎ

 

이 문제는 각 숫자의 연산횟수 최솟값을 저장하는 dp배열을 만들어, dp[n] = min(dp[n-1], dp[n//2], dp[n//3]) 으로 푸는 문제이다. n//2와 n//3은 나누어떨어지는 경우만 가능하기 때문에 그 부분에만 유의해서 풀면 될 것 같다!

 

코드

N = int(input())

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

print(dp[N])

1. 0, 1의 최솟값은 0으로 초기화하여 연산횟수 최솟값 저장하는 배열을 만든다.

2. 2부터 dp[i-1](1 빼는 연산), dp[i//3](3으로 나누는 연산), dp[i//2](2로 나누는 연산) 이 세가지 연산을 했을 때 나오는 최솟값을 비교하여 배열에 저장한다.

3. N의 연산횟수 최솟값을 출력한다.