[백준/Python] 1463_1로 만들기 (Dynamic Programming)

[문제 링크]

1463번: 1로 만들기

---

사용자에게 입력받은 수를 다음과 같은 조건으로 1로 만드는 최소 경우의 수를 찾으면 된다.

 

• 1을 뺀다
• 2로 나누어진다면 2로 나눈다.
• 3으로 나누어진다면 3으로 나눈다.

10을 예시로 들면 10 -> 9 -> 3 -> 1로 총 3번이면 1로 만들 수 있다.

이 문제는 다이내믹 프로그래밍(DP)으로 풀 수 있다. 다이내믹 프로그래밍이란 큰 문제를 작은 문제로 단순화시켜

해결하는 알고리즘이다.

 

10에서 1을 뺐을 경우 9가 된다. 여기서 우리가 만약 9가 1이 되는 최소 횟수를 알고 있다면??

(9가 1이 되는 최소 횟수) + 1 (10에서 1을 빼 9로 갈 때 횟수)을 해주면 쉽게 경우의 수를 찾을 수 있을 것이다.

 

10은 또 2로 나누어질 수 있기 때문에 2로 나누어서 시작하는 경우의 수도 알아보자. 10을 2로 나누면 5가 된다.

이때 5가 1이 되는 최소 횟수를 알고 있다면??

위와 마찬가지로 (5가 1이 되는 최소 횟수) + 1 (10을 2로 나눠 5로 만든 횟수)이 또 다른 경우의 수가 생긴다.

 

이렇게 어떠한 수 N에 대해 최소 경우를 알고 싶다면 다음과 같은 점화식이 만들어진다.

 

dp[N] = min(dp[N-1], dp[N//2] , dp[N//3]) + 1

 

N-1로 시작한 경우 (1을 뺀 경우), N//2로 시작한 경우(2로 나눈 경우), N//3으로  시작한 경우(3으로 나눈 경우)

각각의 경우의 수를 찾아 최소 경우의 수를 찾으면 되는 일이다.

 

그러나 N은 2의 배수일수도,배수일 수도, 3의 배수일 수도, 6의 배수일수도 그 어느 배수도 아닐 수도 있다.

그래서 먼저 '1을 뺀 경우'를 리스트에 저장한 후 2의 배수인지 3의 배수인지에 따라 경우의 수를 비교해준다.

 

0부터 N까지 반복문을 돌면서 경우의 수를 리스트를 저장해두면 저장된 값으로 쉽게 최소 경우의 수를 구할 수 있다.

 

코드가 그리 길지 않으니 전문을 보고 이해하면 훨씬 편할 것이다.

 

N = int(input())
dp_list = [0,0,1,1] # 0 ,1, 2, 3 의 최소 수 미리 저장

for i in range(4, N + 1) :
    # 먼저 1을 뺏을 경우 나오는 경우의 수 저장
    dp_list.append(dp_list[i-1] + 1)

    #2로 나누어질 경우 기존 1을 뺏을 경우의 수와 비교하여 최솟값 저장
    if i % 2 == 0 :
        dp_list[i] = min(dp_list[i], dp_list[i//2] + 1)

    #3으로 나누어질 경우 기존 1을 뺏을 경우의 수와 비교하여 최솟값 저장
    #여기서 2 또는 3으로 나누어질 경우 모든 경우를 봐야하므로 elif가 아닌 if로 설정
    if i % 3 == 0 :
        dp_list[i] = min(dp_list[i], dp_list[i//3] + 1)

print(dp_list[-1])

 

---

이것저것 하느라 알고리즘 공부를 못 했는데, 코테를 보면서 dp와 분할 정복 문제를 풀어야 할 필요성을 느꼈다.

그래서 앞으로는 해당 관련 알고리즘의 기초 문제를 풀어보면서 감을 익혀 나가야겠다.

너무 손 놓고 있었던 것 같기도 하고.... ( 알고리즘 공부 너무 힘들다... )