Dynamic Programing

DP(Dynamic Programing, 동적 계획법)이란 무엇인가? 최근 알고리즘 문제를 집중적으로 풀고 있는데 도통 어떻게 풀어야 할지 모르겠는 문제를 발견했다. 관련 내용들을 찾아보니 Dynamic Programing을 사용해야 한다고 한다. 위키피디아에 정의된 DP란 다음과 같다.

일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다.

필자가 발견한 문제는 백준 알고리즘의 1463번: 1로 만들기였다. 이 문제를 처음 풀었을 땐 정말 단순하게 생각했다. N을 입력 받네? 3으로 나눠지네? 3으로 나눠. 2로 나눠지네? 2로 나눠. 안나눠지네? 1을 빼. 그렇게 줄줄내려와 제시된 케이스엔 맞았지만 당연히 틀렸다. 이러한 최적의 값을 찾아내기 위해선 DP를 활용해야 한다.

이 글은 DP란 개념을 처음 알게 된 필자가 DP와 친해지는 과정을 담은 글이 될 예정이다.


계획하기

일단 문제를 정확하게 파악해보자

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

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

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

문제를 위키피디아에서 정의한 것처럼 여러 개의 하위 문제로 만들어보자. 각각의 숫자를 위 규칙에 의해서 1을 만드려면 어떤 정보가 필요한가?

1
2
3
4
5
6
7
8
9
10
1 => 0
2 => 1
3 => 1
4 => 2로 나누면 2가 됨 => 1 + 1
5 => 1을 빼면 4가 됨 => 1 + (1 + 1)
6 => 2또는 3으로 나눌 수 있으며 두 숫자가 1이 되는 횟수가 같으므로 아무거나 => 1 + 1
7 => 2또는 3으로 나눠지지 않음 1을 빼면 6이 되므로 => 1 + (1 + 1)
8 => 2로 나누면 4가 되므로 => 1 + (1 + 1)
9 => 3으로 나누면 3이 되므로 => 1 + 1
10 => 2로 나누면 5(3) 1을 빼면(2) 이므로 후자가 더 최적 => 1 + (1 + 1)

위와같이 나열하다보니 점차 규칙이 보이는 것 같다. 모든 숫자는 1을 더하거나 2로 나누거나 3으로 나눌 수 있다. 그럼 결국 위에서 계산해 놓은 숫자가 되며 그 중에서 가장 최적의 횟수를 저장하면 된다.


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
min = lambda x, y : x < y and x or y

if __name__=='__main__':
    N = int(input())

    DP = [0 for _ in range((N + 1) * 3)]
    for i in range(1, N+1):
        DP[i + 1] = min(DP[i + 1], DP[i] + 1)
        DP[i * 2] = min(DP[i * 2], DP[i] + 1)
        DP[i * 3] = min(DP[i * 3], DP[i] + 1)
    
    print(DP[N])
WRITTEN BY

배진오

소비적인 일보단 생산적인 일을 추구하며, 좋아하는 일을 잘하고 싶어합니다 :D
im@baejino.com