<1463> 1로 만들기 - DP

 

실버 III

 

문제

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

 

 

입력

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

 

 

출력

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

 

 

풀이

import sys

n = int(sys.stdin.readline().rstrip())

dp = [0] * 1000001

for i in range(2, n + 1):
    dp[i] = dp[i-1] + 1

    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)

print(dp[n])

 

예전에 풀었던 건데, 다시 보니까 역시 모르겠어서 글 남김

역시 난 dp가 너무 어렵다.....

 

결국에는 dp라는 것은, 큰 것을 작은 것으로 나누어서 하나씩 + 해가는 것

그 과정에서 조건에 맞게 취사선택하는 코드를 넣는 것... 

 

뭔가 이 문제를 딱 봤을 때, 인간의 힘으로 비교해서 할 수 없다를 느낀 순간

=> 아 dp 테이블을 만들어서 컴퓨터로 비교를 시켜야겠구나 < 하는 감이 와야 할 것 같음

 

 

1. 우선 받을 수 있는 정수의 크기만큼 dp 테이블 생성 (인덱스 1부터 할거라서 +1 해줌)

2. 1을 만드는 것이니까, dp[1] = 0 일것이고, dp[2]부터 1로 만들 최솟값을 구해줌

3. 2부터 10까지 계산을 해보면

2  => 2 / 2 or 2 - 1
3  => 3 / 3 or (3 - 1) / 2
4 => 4 / 2 / 2 or (4 - 1) / 3
5 => (5 - 1) / 2 / 2
...

 

이런식으로 흘러가는 플로우에서 눈치를 챘어야 함.

4로 예시를 들어보면, 

dp[4] = dp[3] + 1  ==> 1을 빼준 숫자의 최소연산 수 + 1(그 숫자가 되기위해 1을 뺐으니까)

dp[4] = dp[2] + 1  => 2로 나눠지니까, 2로 나눠진 숫자의 최소 연산 수 + 1 (마찬가지로 그 숫자가 되기 위해 나눴으니)

 

==> 내가 받은 이 숫자가 최소의 연산을 하기 위해선, 이 두가지 경우 중 최솟값이 뭔지 비교 해야함

 

** 만약 156216 라는 숫자를 입력 받음. 이걸 1로 만들기 위해서 빼고, 나누고, 비교하고.. 를 어차피 해줘야 하고,

이 과정에서 어떤 숫자가 필요한지 또 계산을 해주어야 함

=> 그럴바에 차라리 시작부터, 최대 받을 수 있는 숫자 만큼 전부 다 for문으로 계산해나가는 것이 효율적..

( dp = [0] * (n+1) 이렇게 해도 되는데, 예전에 왜 저렇게 풀었는지는 모르겠음)

==> 이게 dp의 본질 같음 (그리디랑 비슷하다고 할 수 있음..)

===> 다르게 생각하면, 받을 수 있는 숫자가 명확히 정해져있다? => dp로 풀릴 가능성 높음

 

4. 어쨌든, 2부터 for문을 돌려서 dp[2] = dp[1] + 1 부터 계산 해 놓고,

5. 2로 나눠지는 경우, 3으로 나눠지는 경우에 이렇게 나눠서 계산한 것과, 그냥 1을 뺀 숫자의 최소 연산을 비교해서 더 작은 수를 최소값으로 채택

6. 이런 플로우로 계산을 하다보면 dp[n]에 최소 연산 값이 들어가게 됨