[Python Silver III 1463] 1로 만들기

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

1463번: 1로 만들기

시간 제한	메모리 제한
0.15초	128MB

 

문제

• 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
  
  1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
  2. X가 2로 나누어 떨어지면, 2로 나눈다.
  3. 1을 뺀다.
• 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

입력

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

 

출력

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

 

알고리즘 분류

• 다이나믹 프로그래밍

 

---

 📖 Code

Num = int(input())
val1,val2,val3=0,0,0
dp=[0,1,1,1]

if Num >= 4:
    for i in range(4,Num+1):
    
        val1 = 1 + dp[i-1]
        val2 = 1 + dp[i-1]
        val3 = 1 + dp[i-1]

        if i%3==0:
            val1 = 1 + dp[i//3]
        if i%2==0:
            val2 = 1 + dp[i//2]
           
        dp.append(min(val1,val2,val3))

if(Num==1):
    print(0)
else:
    print(dp[Num])

 ✅ Comment

기준이 되는 숫자를 제외한 4부터 목표로 하는 숫자까지 모두 구해서 dp에 저장한다.

변수 val1, val2, val3를 사용하여 3가지 경우를 만들고.

이중 최솟값만 골라낸다.



10의 경우

1 + dp[i-1] 의 값은 3이다.

val1 , val2 , val3 = 3 이고

10은 2로 나누어지게 되니 val2의 값이 바뀌게 된다.

val2 의 값은 1 + dp[5]

이때 dp[5] 값은 미리 계산이 되어있다 dp[5] 값은 3이고

val2의 값은 4가 된다.



10의 경우

10 -> 5 -> 4 -> 2 -> 1

이런 식으로 2로 바로 나누는 것보다.

10 -> 9 -> 3 -> 1

1을 먼저 뺸뒤 3으로 나누는 게 

횟수가 더 적어지게 된다.



이렇게 다양한 경우가 나오게 되는데.



위의 코드를 사용하게 되면 모든 경우를 확인하며 

해당하는 숫자에 저장이 됩니다.