Dynamic Programming

DP recover

큰 문제를 같은 구조의 작은 문제로 쪼개서, 그 답을 저장해 두고 재활용한다!

핵심 2가지

1. 점화식(재귀 관계) 세우기.
   • ex) dp[i] = dp[i-1] + dp[i-2]
2. Memoization(저장)
   • 이미 계산한 값은 배열이나 표에 저장.
   • 다시 쓸 때는 저장된 값 꺼내기.

접근 방식

• Top-down (재귀 + Memoization) : 재귀로 풀되, 계산한 건 캐시에 저장.
• Bottom-up (반복문) : 작은 문제부터 차례차례 쌓아올림.

Example : 계단 오르기

• 계단이 N칸 있고, 한 번에 1 or 2칸만 오를 수 있다면?

경우의 수 = dp[n]

dp[0] = 1		// (아무것도 안 올라간 경우)
dp[1] = 1		// 1칸 올라갈 수 있는 경우의 수
dp[n] = dp[n-1] + dp[n-2]		// 마지막에 1칸 올라갔거나, 2칸 올라갔거나.

---

Example from SWEA

삼성 SWEA - DP
N개의 숫자 쌍이 주어진다. 숫자 쌍은 두 개의 숫자로 이루어져 있으며, 첫 번째 숫자를 x라고 하고, 두 번째 숫자를 y라고 했을 때 (x, y)로 표현할 수 있다. 이때 x는 1 또는 2로만 주어지고 y값은 1부터 100이하의 정수만 주어진다. N개의 숫자 쌍의 일부를 선택하여 x값들의 합을 Sx라고 하고, 선택되지 않은 나머지 숫자 쌍들의 y값들의 합을 Sy라고 할때, Sx ≥ Sy 를 만족해야 한다.

예를 들어 N이 5인 숫자 쌍이 (x0, y0), (x1, y1), (x2, y2), (x3, y3), (x4, y4) 와 같이 주어진 경우 0, 2, 4번째 숫자 쌍을 선택했을 경우 x0+x2+x4 ≥ y1+y3 가 성립되어야 한다. 주어진 N개의 숫자 쌍 중, 위의 규칙에 맞게 숫자 쌍을 선택하는 방법 중, 선택된 숫자 쌍의 x의 합이 최소가 되는 경우를 찾고, 이 경우의 x의 합을 구하라.

1) N은 1이상 1,000 이하의 정수. (1 ≤ N ≤ 1,000)
2) 숫자 쌍 (x, y) 의 x, y 는 각각 1 ≤ x ≤ 2와 1 ≤ y ≤ 100를 만족하는 정수

---

#include <stdio.h>

#define MAX_X 2
#define MAX_N 1001

int N;
int num_pair[MAX_N][2];

int dp[MAX_N][MAX_X * MAX_N];

int max(int a, int b) {
    return (a > b) ? a : b;
}

int solve() {
    int ans = 0;
    // dp initialization
    for (int i = 0; i < MAX_N; i++) {
        for (int j = 0; j < MAX_N * MAX_N; j++) {
            dp[i][j] = 0;
        }
    }

    // set maximum x_sum as ans
    for (int i = 0; i < N; i++) {
        ans += num_pair[i][0];
    }

    // Initialize accesible space as -1, indicating not accessed before
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < ans; j++) {
            dp[i][j] = -1;
        }
    }

    // Initial value
    dp[0][ans] = 0;
    dp[0][ans - num_pair[0][0] - num_pair[0][1]] = num_pair[0][0];

    // DP transition
    for (int i = 1; i < N; i++) {
        int sum = num_pair[i][0] + num_pair[i][1];
        for (int j = 0; j <= ans; j++) {
            // if prev dp is available
            if (dp[i - 1][j] != -1) {
                int diff = j - sum;
                if (diff >= 0) {
                    // choose update
                    dp[i][diff] = max(dp[i][diff], dp[i - 1][j] + num_pair[i][0]);
                }
                // not choose update
                dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            }
        }
    }


    int max_value = -1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= ans; j++) {
            max_value = max(max_value, dp[i][j]);
        }
    }
    return ans - max_value;
}

int main(void)
{
    int T;
    scanf("%d", &T);
 
    for (int test_case = 1; test_case <= T; test_case++)
    {
        scanf("%d", &N);
 
        for (int i = 0; i < N; i++)
        {
            scanf("%d %d", &num_pair[i][0], &num_pair[i][1]);
        }
        printf("#%d %d\n", test_case, solve());
    }
    return 0;
}