EDOC 2024-1 7회차 정모 (동적 계획법 알아보기 4)

A. 악수 (백준 8394번)

 

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

 

//C++

#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> dp = vector<int>(n + 1);
    
    dp[0] = 0;
    dp[1] = 1;
    if (n >= 2) {
        dp[2] = 2;
    }

    for (int i = 3; i < n + 1; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 10;
    }

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

(정답)

 

---

 

B. 가장 큰 감소하는 부분 수열 (백준 17216번)

 

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

 

//C++

#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 = vector<int>(n + 1);
    a[0] = 0;
    for (int i = 1; i < n + 1; i++) {
        cin >> a[i];
    }

    vector<int> dp = vector<int>(n + 1);
    dp[0] = 0;
    int maxa = 0;

    for (int i = 0; i < n + 1; i++) {
        int maxt = 0;
        for (int j = 0; j < i; j++) {
            if (a[j] > a[i]) {
                maxt = max(maxt, dp[j]);
            }
        }
        dp[i] = maxt + a[i];
        maxa = max(maxa, dp[i]);
    }

    cout << maxa << '\n';
}

(정답)