[ICPC Sinchon] 25W 알고리즘 캠프 초급 강의 9회차 과제 에디토리얼

9회차 - dp

 

---

</2748> 피보나치 수 2

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

피보나치 수를 구하는 걸 재귀로 구현하게 되면 시간 복잡도가 O(2^n)이므로 n이 조금만 커져도 실행 시간이 기하급수적으로 늘어나게 됩니다. 이는 같은 피보나치 값을 여러 번 중복 계산하기 때문입니다. 예를 들어, fib(5)를 계산할 때 fib(3)이 두 번, fib(2)가 세 번 호출되는 식으로 불필요한 연산이 계속 발생합니다.

따라서 중복 계산을 막기 위해 이전에 계산한 값들을 저장하고 활용해야 합니다. 이럴 때 사용하는 대표적인 방법이 동적 계획법(DP)를 사용하게 되는 것입니다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    
    vector<long long> fib(n + 1);
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i < n + 1; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    cout << fib[n] << '\n';
}

 

---

</2156> 포도주 시식

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

dp 배열의 정의

dp[i] : i번째 잔까지 고려했을 때 최대로 마실 수 있는 포도주 양

점화식

dp[i] = max(dp[i - 1], dp[i - 2] + a[i], dp[i - 3] + a[i - 1] + a[i]);

- dp[i - 1] → 현재 잔(i)을 마시지 않는 경우

- dp[i - 2] + a[i] → 현재 잔(i)을 마시고, 바로 직전 잔(i-1)을 마시지 않은 경우

- dp[i - 3] + a[i - 1] + a[i] → 현재 잔(i)을 마시고, 바로 직전 잔(i-1)도 마셨지만, i-2번 잔은 마시지 않은 경우

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<int> a(n + 1);
    for (int i = 1; i < n + 1; i++) cin >> a[i];

    vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = a[1];
    if (n > 1) dp[2] = a[1] + a[2];

    for (int i = 3; i < n + 1; i++) {
        dp[i] = max(max(dp[i - 1], dp[i - 2] + a[i]), dp[i - 3] + a[i - 1] + a[i]);
    }

    cout << dp[n] << '\n';
}

 

---

</11048> 이동하기

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

전형적인 2차원 DP 문제입니다.

이 문제에서 함정 아닌 함정은 대각선 이동은 무조건 손해라는 것입니다. 그 이유는 사탕을 한 번 더 먹고 가는 길이 항상 존재하기 때문입니다. 다른 말로 표현하자면, 사탕의 개수는 항상 0보다 크거나 같으므로 대각선으로 간다면 더 많은 칸을 지나가는 길을 선택하는 것이 항상 유리합니다.

따라서 점화식은 다음과 같습니다.

a[i][j] += max(a[i - 1][j], a[i][j - 1]);

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> a;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    a = vector<vector<int>>(n, vector<int>(m));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    for (int i = 1; i < n; i++) a[i][0] += a[i - 1][0];
    for (int j = 1; j < m; j++) a[0][j] += a[0][j - 1];

    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            a[i][j] += max(a[i - 1][j], a[i][j - 1]);
        }
    }

    cout << a[n - 1][m - 1] << '\n';
}

 

---

</17520> Balanced String

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

dp 배열의 정의

- dp1[i]: 길이 i+1의 이진 문자열 중 0의 개수가 1개 더 많은 문자열의 개수

- dp2[i]: 길이 i+1의 이진 문자열 중 0과 1의 개수가 같은 문자열의 개수

- dp3[i]: 길이 i+1의 이진 문자열 중 1의 개수가 1개 더 많은 문자열의 개수

점화식

- dp1[i] (0이 1개 더 많은 경우)

  dp2[i-1]에 "0"을 붙이면 0이 1개 더 많아짐

  ⇒ dp1[i] = dp2[i-1]

- dp2[i] (0과 1의 개수가 같은 경우)

  dp1[i-1]에 "1"을 붙이면 0과 1의 개수가 같아짐

  dp3[i-1]에 "0"을 붙이면 0과 1의 개수가 같아짐

  ⇒ dp2[i] = (dp1[i-1] + dp3[i-1]) % mod

- dp3[i] (1이 1개 더 많은 경우)

  dp2[i-1]에 "1"을 붙이면 1이 1개 더 많아짐

  ⇒ dp3[i] = dp2[i-1]

#include <iostream>
#include <vector>
using namespace std;

int mod = 16769023;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<int> dp1(n + 1); // 0의 개수가 1개 더 많은 이진 문자열 수
    vector<int> dp2(n + 1); // 0의 개수와 1의 개수가 같은 이진 문자열 수
    vector<int> dp3(n + 1); // 1의 개수가 1개 더 많은 이진 문자열 수

    dp1[0] = 1;
    dp2[0] = 0;
    dp3[0] = 1;

    for (int i = 1; i < n; i++) {
        dp1[i] = dp2[i - 1];
        dp2[i] = (dp1[i - 1] + dp3[i - 1]) % mod;
        dp3[i] = dp2[i - 1];
    }

    cout << (dp1[n - 1] + dp2[n - 1] + dp3[n - 1]) % mod << '\n';
}

 

---

</9465> 스티커

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

스티커 배열

stk[2][n+1] 배열에 스티커 점수를 저장

dp 배열의 정의

dp[i][j] : (i, j) 스티커를 포함했을 때 얻을 수 있는 최대 점수

점화식

- dp[0][i] = max(dp[1][i - 1], dp[1][i - 2]) + stk[0][i];

  → (0, i)에 있는 스티커를 선택하려면 이전 스티커 선택은 (1, i - 1) 또는 (1, i - 2) 가능

- dp[1][i] = max(dp[0][i - 1], dp[0][i - 2]) + stk[1][i];

  → (1, i)에 있는 스티커를 선택하려면 이전 스티커 선택은 (0, i - 1) 또는 (0, i - 2) 가능

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<vector<int>> stk(2, vector<int>(n + 1));
        for (int i = 0; i < 2; i++) {
            for (int j = 1; j < n + 1; j++) {
                cin >> stk[i][j];
            }
        }

        vector<vector<int>> dp(2, vector<int>(n + 1, 0));
        dp[0][1] = stk[0][1];
        dp[1][1] = stk[1][1];

        for (int i = 2; i < n + 1; i++) {
            dp[0][i] = max(dp[1][i - 1], dp[1][i - 2]) + stk[0][i];
            dp[1][i] = max(dp[0][i - 1], dp[0][i - 2]) + stk[1][i];
        }

        cout << max(dp[0][n], dp[1][n]) << '\n';
    }
}

 

---

</11057> 오르막 수

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

dp 배열의 정의

dp[i][j] : 길이가 i이고 마지막 숫자가 j일 때 가능한 오르막 수의 개수

점화식

dp[i][j] = dp[i - 1][0] + … + dp[i - 1][j]

#include <iostream>
#include <vector>
using namespace std;

int MOD = 10007;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<vector<int>> dp(n + 1, vector<int>(11, 0));

    // dp 배열 초기화
    for (int j = 1; j < 11; j++) dp[1][j] = 1;

    for (int i = 2; i < n + 1; i++) {
        for (int j = 0; j < 11; j++) {
            for (int k = 0; k <= j; k++) {
                dp[i][j] += dp[i - 1][k];
                dp[i][j] %= MOD;
            }
        }
    }

    int ans = 0;
    for (int j = 1; j < 11; j++) {
        ans += dp[n][j];
        ans %= MOD;
    }
    cout << ans << '\n';
}

 

---

</10422> 괄호

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

dp 배열의 정의

dp[i][j] : 길이가 i이고, 열린 괄호 개수가 j인 경우의 수

점화식

dp[i][j] = dp[i − 1][j − 1] + dp[i − 1][j + 1]

- dp[i - 1][j - 1] : 이전 단계에서 j - 1개의 열린 괄호가 있고 (를 추가한 경우

- dp[i - 1][j + 1] : 이전 단계에서 j + 1개의 열린 괄호가 있고 )를 추가한 경우

#include <iostream>
#include <vector>
using namespace std;

int MAX_LEN = 5000;
int MOD = 1000000007;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;

    vector<vector<int>> dp(MAX_LEN + 1, vector<int>(MAX_LEN + 1, 0));

    dp[1][1] = 1;
    for (int i = 2; i < MAX_LEN + 1; i++) {
        dp[i][0] = dp[i - 1][1];
        for (int j = 1; j < MAX_LEN; j++) {
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;
        }
        dp[i][MAX_LEN] = dp[i - 1][MAX_LEN - 1];
    }

    while (t--) {
        int l;
        cin >> l;


        cout << dp[l][0] << '\n';
    }
}