동적 계획법 practice01_1로 만들기

 

백준 1436번

 

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

1463번: 1로 만들기

 

1. 문제

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

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

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

 

 

2. 내가 작성한 알고리즘

 

inp=int(input())
 
x=[0]*(inp+1)
 
for i in range(2,inp+1):
    x[i]=x[i-1]+1
 
    if i%3==0:
        x[i]=min(x[i],x[i//3]+1)
    if i%2==0:
        x[i]=min(x[i],x[i//2]+1)
 
print(x[inp])
 
 

 

3. 이번 알고리즘을 통해 배운 점

 

이번 문제는 단계적으로 소분할하여 문제를 풀어가야 했다. 시간 복잡도가 계속 걸려 문제를 풀지 못했지만

답을 보고 해석하니 생각보다 단순했다.

 

1을 만들기 위해서 해야 할 방법은

 1). 1로 빼기    2). 3으로 나누기   3). 2로 나누기 이다. 

while(num!=1) 을 사용하여 단순히 반복을 하면 좋은 시간 복잡도가 나오지 못한다.

그래서 동적 계획법을 사용한다. 배열을 통해 패턴이 있는 숫자의 카운트를 각 배열의 인덱스에 누적한다.

우리가 알아야 할 것은 단순히 나누기 2,3이 아닌 -1을 했을 때 나누기 2,3을 하는게  더 효율적인가를 알아야 한다.

 

다음 표를 확인해보겠다. 

숫자	방법	숫자	방법
2	/2	3	/3
4	/2 /2 or -1 /3	5	-1 /2 /2 or -1 -1 /3
6	/3 /2 or /2 /3	7	-1 /3 /2 or -1 /2 /3
8	/2 /2 /2	9	-1 /2 /2 /2  or /3 /3

 

여기 표에서는 패턴이 있다. 숫자 (4,5) ( 6,7) (8,9) ..그사이는 단 -1 하나 밖에 차이가 나지 않는다. 또한

숫자 (2,4) (3,6) (4,8) (3,9).. 그 사이는 단 /2 또는 /3 단 하나 밖에 차이가 나지 않는다.

여기서 알 수있는 공식은 nums[i]=nums[i-1]+1 이다.

해당 공식은 숫자 3 이후 부터는 -1 을 수행한 것으로 보면 된다.

위에서 설명한 것 과 같이 우리가 알고 싶은 것은 나누기 2,3을 하는 것과 -1 이후 나누기 2,3을 비교하는 것이다. 

여기서 알 수 있는 공식은 nums[i]=min(nums[i], nums[i/3]+1) 이다. (i/3 에 +1을 하는 이유는 카운트하기 위해서 이다.)