[python/파이썬] 백준 1463 1로 만들기

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

2

예제 출력 1 복사

1

예제 입력 2 복사

10

예제 출력 2 복사

3

힌트

10의 경우에 10 -> 9 -> 3 -> 1로 3번 만에 만들 수 있다.

 

[문제 풀이]

 

바로 이전에 올렸던 문제와 비슷한 방법으로 풀리는 문제이다.

나누기 2 혹은 나누기 3 혹은 빼기 1 연산을 통해서 1을 만들 때 

가장 적은 횟수로 만들 수 있는 경우를 구하는 문제이다.

 

일단 dp로 풀었기에

초기값을 저장해준다.

0과 1일 때는 0으로 저장해주고

n이 2와 3일 때도 한 번의 연산(나누기)으로 1을 만들 수 있으므로 1을 저장해준다.

 

그 후에 for문을 돌면서 dp값들을 채워준다.

 

2로 나눠진다면 

dp[i/2]와 현재 min_value를 비교하여 더 작은 값을 min_value로 저장한다.

3으로 나눠진다면

dp[i/3]와 현재 min_value를 비교하여 더 작은 값을 min_value로 저장한다.

그리고 마지막으로 

dp[i-1]와 현재 min_value를 비교하여 더 작은 값을 min_value로 저장한다.

 

즉 이전에 저장한 dp값을 통해 i번째 dp 값을 구하는 과정이다.

 

예를 들어

i = 7 일 때

i는 3이나 2로 나눠지지 않기에 -1 연산을 해준다

그러면 6이 되고 여기서부터의 계산은 dp[6]의 값과 같다.

따라서 7에서 6이 되기 위해 -1 연산을 해주었기에

dp[7] = dp[6] +1 

 

또 다른 예를 들어보면 

i = 12 일 때

i는 3으로도 나눠지고, 2로도 나눠진다

dp[i/3] = dp[4] = 2

dp[1/2] = dp[6] = 2

dp[i-1] = dp[11] = 4 

이므로 이 중에 가장 작은 값인 2를 선택해야 한다.

즉 12라는 값은 3으로 나누거나 2로 나누는 방법 중에 어느 것을 선택해도 최솟값이 가능하다는 것이다.

따라서

dp[12] = 2 + 1 = 3

 

[소스 코드]

n = int(input())

dp = [0,0,1,1] #2와 3은 1번의 나누기 연산으로 1을 만들 수 있다.

for i in range(4, n+1): #4부터 계산 
    min_value = 1e9 #충분히 큰 값으로 min값을 설정

    if i%2==0: #2로 나눠진다면 2로 나눈 값에 대한 dp값과 현재 min 값을 비교해 min값을 결정
        min_value = min(min_value, dp[i//2])
    if i%3==0: #3으로 나눠진다면 3으로 나눈 값에 대한 dp값과 현재 min 값과 비교해 min값을 결정
        min_value = min(min_value, dp[i//3])
    min_value = min(min_value, dp[i-1]) #-1한 값에 대한 dp값과 현재 min값과 비교해 min값을 결정
    
    dp.append(min_value + 1) #나누거나 뺀 연산의 횟수를 min값에 더해서 i번째 dp값에 저장한다
print(dp[n])