[백준] 1463번 1로 만들기 (Python)

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

1463번: 1로 만들기

---

풀이 과정

①문제 바라보기

처음에 이 문제가 Greedy 문제인 줄 알았다. 그러나 알고보니 DP문제! 뭔가 greedy로 풀릴 것 같기도하다.

이 문제도 메모이제이션 기법으로 풀릴 것이다.

 

문제에서 내가 할 수 있는 조치는 다음과 같다.

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

 

②아이디어 펼치기

자명한 사실이 있다. N을 만드는 데 x번의 단계가 필요하다면 그냥 -1만 가능하다고 할 때, N+1은 x+1단계가 필요하다.

 

이 문제를 풀기 위해서는 dp 테이블이 필요하고  for문을 돌려줘야한다.

이때 for문의 index값을 최대한 활용하는 것이 정신건강에 좋다. 왜냐하면, i%2==0이거나 i%3==0 인 경우로 문제를 분할시키면 굉장히 편리하기 때문이다. 그래서 dp[i//2] 혹은 dp[i//3]을 호출해주면 거기다가 +1만 하면 필요한 단계가 말끔히 나오기 때문이다!

 

논외로, %2와 %3 둘 다 0이 되는 경우가 있는데!  이 경우 때문에 elif를 쓰면 안된다. 둘 다 되는 경우 두 방법 다 실험을 해봐야 한다. 당연히! 그래서 %2일 때 더 작은 값을 저장해놓고 %3일 때 값을 또 탐색해서 비교하게 된다.

 

③전체 코드

N = int(input())
dp = [0]*(N+1)

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

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

print(dp[N])