백준 1463번 1로 만들기

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

1463번: 1로 만들기

 

문제

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

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

 

입력

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

 

출력

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

 

from cmath import inf
n = int(input())


count_list=[inf]*(n+1)

for i in range(2, n+1):
    if i==2 or i==3:
        count_list[i]=1    
    else:
        if i%6==0:
            count_list[i] = min(count_list[i//3]+1,count_list[i//2]+1, count_list[i-1]+1)
        elif i%3==0:
            count_list[i] = min(count_list[i//3]+1, count_list[i-1]+1)
        elif i%2==0:
            count_list[i] = min(count_list[i//2]+1, count_list[i-1]+1)
        else:
            count_list[i] = count_list[i-1]+1
            
if n==1:
    print(0)
else:
    print(count_list[n])

 

문제를 풀면서 이전에 풀었던 DP문제인 설탕배달(2839)을 참고하면서 풀었는데 풀이법이 거의 동일하다.

혹시 이 문제를 풀지 못하겠다며 먼저 풀고오는걸 추천한다.

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

2839번: 설탕 배달

 

문제 풀이

DP는 푸는 방식이 위에서 부터 내려오는 방식과 아래에서 부터 값을 채워나가는 방식이 있다.

이 중 아래에서 부터 값을 채워나가는 바텀 업 방식 방식을 사용하였다.

 

먼저 입력값 만큼의 list를 생성하여 inf로 채워주었다.

값은 바텀 업 방식 + 모든 경우에 대한 처리가 되있으므로 0으로 초기화하여도 큰 문제가 없다.

 

이후 2부터 n의 범위까지 2와3을 1로 채우며

그 이상의 수는 모든 경우의 수를 고려하여 가장 적은 count값을 가지도록 하였다. 

• 값이 6으로 나눠떨어 지는 경우에는 n/3, n/2, n-1의 리스트 중 가장 작은 값을 가져오게 했으며
• 2와3으로 나눠떨어지는 경우 역시 같은 방식을 사용하였다.
• 어떠한 값으로도 나누어 떨어지지 않을때에는 n-1의 카운트를 가져왔다.

위 반복문을 통하여 모든 리스트에는 1로 만들어질때까지의 최소의 카운트로 값이 채워진다.

이후 1일 경우 0을 출력하고

그렇지 않은경우 리스트[n]의 값 list에서 가져오면 n이 1이 될때까지의 최소 연산 수를 구할 수 있다.