[백준 1463 🥈] 1로 만들기

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

1463번: 1로 만들기

문제

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

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

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

입력

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

출력

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

문제 풀이

• BFS로 풀까..? 했지만 입력의 최대 범위가 10^6인 것을 보고 DP로 풀어야겠다 생각했다.
• DP로 푸는 것이 훨씬 간단하게 풀린다!
• dp[num]은 num을 1로 만드는 데에 필요한 최소 연산 횟수를 의미한다.
• dp[1]은 아무런 연산을 해주지 않아도 이미 1이므로 0을 저장하고, dp[2]부터 dp[n]까지 값을 넣어주면 된다.
• 3과 2 모두 나눠떨어질 수 있는 6, 12, 18,.. 과 같은 수들은 1,2,3번 연산을 모두 수행할 수 있다.
  • 3으로 나눈 수의 dp 값 / 2로 나눈 수의 dp 값 / 1을 빼준 수의 dp 값 중 가장 작은 값을 선택하고 +1을 해서 해당 연산을 수행한 횟수 1을 더해서 dp 값을 갱신해준다.
• 다음으로 3으로만 나눠떨어지는 경우엔 1번 연산과 3번 연산을 수행할 수 있다.
  • 3으로 나눈 수의 dp 값 / 1을 빼준 수의 dp 값 중 작은 값을 선택하고 해당 연산을 수행한 횟수 1을 더해서 dp 값을 갱신한다.
• 2로만 나눠떨어지는 경우도 위와 동일한 방식으로 2로 나눈 수의 dp 값 / 1을 빼준 수의 dp 값 중 작은 값을 선택해서 dp 값을 갱신한다.
• 3과 2 모두 나눠떨어지지 않는 경우엔 3번 연산만 수행가능하므로 1을 빼준 수의 dp 값에 1을 더해서 dp값을 갱신해준다.
• 이러한 과정을 모두 거쳐서 dp[n] 값을 출력해주면 끝!

import sys

n=int(sys.stdin.readline())

dp=[0]*(n+1)
dp[1]=0
for i in range(2,n+1):
    # 3과 2로 모두 나누어 떨어질 경우
    if i % 3 == 0 and i % 2 == 0:
        dp[i]=min(dp[i//3], dp[i//2], dp[i-1])+1
    elif i%3==0:
        dp[i]=min(dp[i//3], dp[i-1])+1
    elif i%2==0:
        dp[i]=min(dp[i//2], dp[i-1])+1
    else:
        dp[i]=dp[i-1]+1

print(dp[n])