[알고리즘]백준 1463번: 1로 만들기

알고리즘 유형: 다이나믹 프로그래밍 

문제

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

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

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

입력

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

출력

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

 

출력

---

좀 까다로웠던 문제였습니다. 

 

처음에는 탐욕법을 먼저 생각했었는데요 아이디어는 다음과 같았습니다 

연산1. 3으로 나누기 연산2. 2로 나누기 연산3. 1 빼기의 세가지 연산 중에서

가장 숫자를 크게 감소 시키는 순이 1, 2,3 순이므로 3으로 나눌수 있으면 나눔 or not 2로 나눔 or not 1을 빼줌 

 

그런데 10의 예로 보면 2로 나눠줄 수 있기 때문에 나눠준 후 연산을 추적해보면

10->5->4->2->1 이므로 총 연산은 4회인데 

1을 빼주고 시작하면 

10->9->3->1 총 연산 3회로 더 빨리 끝나는 것을 확인 할 수 있었습니다.  

 

사실 잘 생각해보면 탐욕법의 전제에 맞지 않는 문제입니다. 

탐욕법은 현재의 선택의 결과가 나중의 선택에 영향을 안줘야하는데 

이 문제는 지금 선택한 연산에 따라 다음번 선택가능한 연산 바뀌기 때문입니다.

 

그래서 DP를 이용해 풀이를 해주었습니다

 

최소한의 배열은 있어야하므로, 먼저 필요한 각 숫자마다 필요한 연산 횟수를 담은 nums를 만들어줍니다 

이때 nums[n]을 출력했을때 n을 1로 만드는데 필요한 연산 횟수를 출력하기 위해서 배열의 맨 앞에 

의미없는 숫자인 0를 집어넣어줍시다.

 

조건은 크게 3가지입니다 

 

1. 3으로 나누어지는 경우 

 

2로도 나누어지는지 확인 하고 nums[i//2]+1과 nums[i//3]+1 중에서 더 작은 것을 배열에 추가 

2로 나누어지지 않는다면 1+nums[i-1],1+nums[(i//3)]에서 작은 것을 추가 

 

2. 2로만 나누어지는 경우(3으로 나누어지지 않음) 

 

1+nums[i-1],1+nums[(i//2)]에서 작은 것을 추가 

 

3.2와 3 모두 나누어떨어지지 않는 경우 

 

1+nums[i-1]을 배열에 추가합니다 

 

함수는 배열의 -1번째 원소를 return하는데 

n이 6보다 크거나 같은 경우에는 n번째 원소를 return합니다

(실제로 이 문제의 90%대에는 이 케이스를 거르기 위한 테스트케이스가 포함되어 있는거 같습니다) 

import sys 
n = int(sys.stdin.readline().strip())
def count(n): 
    nums = [0,0,1,1,2,3,2]
    for i in range(7,n+1):
        if i%3==0:
            if i%2==0:
                nums.append(min([1+nums[i//3], 1+nums[i//2],1+nums[i-1]]))
            else: 
                nums.append(min(1+nums[i-1],1+nums[(i//3)]))
        if i%2==0 and i%3!=0:
           
            nums.append(min([1+nums[(i//2)],1+nums[i-1]]))
        if i%2!=0 and i%3!=0:
            nums.append(1+nums[i-1])
    if n<=6:
        return nums[n]
    else:
        
        return nums[-1]
print(count(n))