백준 알고리즘, 1463 문제

---

개요

이 문제는 Dynamic Programming 의 첫번째 문제다.

Dynamic Programming 은 반복되는 연산을 매번 하지않고 배열이나 힙 등의 저장 공간에 저장해두었다가 필요할때 사용하는 알고리즘이다.

이러한 특징 때문에 이광근 교수님이 지은 "컴퓨터 공학이 여는 세계" 에는 Dynamic Programming 이 "기억하며 풀기" 라고 설명되어 있다.

학교 수업에서도 Dynamic Programming 은 Dynamic 과 거리가 멀다고 배웠는데, 적절한 번역이라고 생각한다.

동적 계획법 이라고 하면 전혀 감이 오지않지만, "기억하며 풀기" 라고 한다면 한번에 이해가 되는 기분이다.

---

시행착오

다음을 기억하려 했다.

1. X 를 3 으로 나누는 연산

2. X 를 2 로 나누는 연산

3. X 를 1 로 빼는 연산

배열이 3개 필요하고 어떤 값 X 가 1 이 되는 최소값을 찾으려면 3! 의 모든 값을 비교하여 최소를 찾아야 하나 생각했다. 접근하기 어려웠다.

---

해결

연산을 기억하는 것이 아니라 답을 기억하는 것이 가장 효율적이다.

배열에 해당 index 가 1 이 되는 최소값을 저장한다.

DP[1] = 0;
DP[2] = 1;
DP[3] = 1;
DP[4] = 2;
DP[5] = 3;
DP[6] = 2;

1 (index) 이 1 이 되는 최소 연산의 횟수는 0 번 이므로 DP[1] 은 0 이다.

2 (index) 가 1 이 되는 최소 연산의 횟수는 1 번 이므로 DP[2] 은 1 이다.

3 (index) 이 1 이 되는 최소 연산의 횟수는 1 번 이므로 DP[3] 은 1 이다.

4 (index) 가 1 이 되는 최소 연산의 횟수는 2 번 이므로 DP[4] 은 2 이다.

5 (index) 이 1 이 되는 최소 연산의 횟수는 3 번 이므로 DP[5] 은 3 이다.

6 (index) 이 1 이 되는 최소 연산의 횟수는 2 번 이므로 DP[6] 은 2 이다.

DP 배열은 이렇게 구성된다.

그럼 이제 DP 배열에 저 값들을 저장시킬 점화식을 설계하면 된다.

손계산을 해보자.

예시로 5 를 들겠다.

5 를 1 로 만들려면 총 3 번의 연산이 최소값이 되는데, 그 과정은 다음과 같다.

1. 5 - 1 = 4          

2. 4 / 2 = 2

3. 2 / 2 = 1

이렇게 3 번의 과정을 거치면 5 가 1 이 되는 총 연산의 횟수인 3 번이 나온다.

그러나 이렇게 구할 수 도 있다.

1. 5 - 1 = 4 ---> 여기서 4 가 나왔으니, 4 가 1 이 되는 최소 연산의 횟수 + 1 이 5 의 최소 연산 횟수가 된다.

+ 1 을 해주는 이유는 5 - 1 연산을 했으니, 그 연산 횟수를 더해주는 것이다.   

이 생각을 해내었으면 점화식을 설계할 수 있다.

// 5 가 1 이 되는 최소 연산의 횟수는 4 가 1이 되는 최소 연산의 횟수 + 1 이다.
// i 가 1 이 되는 최소 연산의 횟수는 i - 1 이 1 이 되는 최소 연산의 횟수 + 1 이다.

DP[i] = DP[i - 1] + 1;  

먼저 이 계산을 가장 처음하고나서, 다음 2 가지의 경우를 고려하여 DP 배열에 최소값을 저장해주면 된다.

이번에는 6 을 예시로 들어 이해해보겠다.

1. i 가 2 로 나누어지는 경우

DP[i] 를 DP[i / 2] 가 1 이 되는 최소 연산 횟수 + 1 을 한 후 DP[i] 와 비교하여 최소값을 저장한다.

DP[i] = DP[i - 1] + 1; 에 의해서 DP[6] 에는 4 가 저장되어 있다. (DP[5] = 3 이므로)

그런데 6 은 2 로 나누어지므로 만약 6 / 2 의 연산을 한 이후라면, DP[3] 의 값에 + 1 을 해주면 최소 연산 횟수가 된다.

(+1 을 해주는 이유는 6 / 2 연산을 했기 때문이다.)

그래서 우리는 처음에 저장되었던 DP[6] = 4 와 이후에 나누기 연산을 통해 얻어진 값인 DP[6] = 2 중에서 최소값을 DP[6] 에 다시 저장해주면 된다.

2. i 가 3 으로 나누어지는 경우

1 번 내용을 이해했다면, 나누는 값을 3 으로 해주면 된다는 것을 알 것 이다.

이후의 식은 다음과 같은 모습이다.

DP[i] = DP[i - 1] + 1;
if (i % 2 == 0) DP[i] = min( DP[i], DP[ i / 2] + 1);
if (i % 3 == 0) DP[i] = min( DP[i], DP[ i / 3] + 1);

---

코드

@github 에서 확인하기

/**
 * @site: https://www.acmicpc.net/problem/1463
 * @github: https://github.com/7772
 * @auth: Landon Park
 * @date: 2018. 07. 17
 */
#include <iostream>
using namespace std;
int min(int a, int b) {
    return (a < b) ? (a) : (b);
}
int main() {
    int i;
    int N;
    int DP[1000001];
    cin >> N;
    DP[0] = DP[1] = 0;
    for (i = 2; i <= N; i++) {
        DP[i] = DP[i - 1] + 1;
        if (i % 2 == 0) DP[i] = min(DP[i], DP[i / 2] + 1);
        if (i % 3 == 0) DP[i] = min(DP[i], DP[i / 3] + 1);
    }
    cout << DP[N] << endl;
    return 0;
}