[이취코] 8. DP - C++

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

long long dp[100];

int main() {
    //1. 피보나치
    int n = 50;
    d[1] = 1;
    d[2] = 1;
    
    for (int i = 3; i <= n; i++) {
        d[i] = d[i-1] + d[i-2]; // 재귀 아님
    }
    cout << d[n];

    //2. 1로 만들기 - bottom up
    //int x = 26;
    //for (int i = 2; i <= x; i++) {
    //    d[i] = d[i - 1] + 1; // 1 빼는 경우
    //    if (i % 2 == 0) {
    //        d[i] = min(d[i], d[i / 2] + 1);
    //    }
    //    if (i % 3 == 0) {
    //        d[i] = min(d[i], d[i / 3] + 1);
    //    }
    //    if (i % 5 == 0) {
    //        d[i] = min(d[i], d[i / 5] + 1);
    //    }
    //}
    //cout << d[x];

    //2. 1로 만들기
    //int x;
    //cin >> x;
    //
    //for (int i = 2; i <= x; 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);
    //    }
    //    if (i % 5 == 0) {
    //        dp[i] = min(dp[i], dp[i / 5] + 1);
    //    }
    //}
    //cout << dp[x];

    //3. 개미 전사
    //int n;
    //vector<int> arr;
    //
    //cin >> n;
    //for (int i = 0; i < n; i++) {
    //    int num;
    //    cin >> num;
    //    arr.push_back(num);
    //}
    //dp[0] = arr[0];
    //dp[1] = max(arr[0], arr[1]);
    //for (int i = 2; i < n; i++) {
    //    dp[i] = max(dp[i - 2] + arr[i], dp[i - 1]);
    //}
    //cout << dp[n - 1];

    //4. 바닥공사
    //int n;
    //cin >> n;
    //
    //dp[1] = 1;
    //dp[2] = 3; //사각형 1개, 가로긴거 2개, 세로긴거 3개 => 총 3개
    //for (int i = 3; i <= n; i++) {
    //    dp[i] = dp[i - 2] * 2 + dp[i - 1]; //사각형, 가로긴거 정해져있어서 양옆으로 세로 추가되거나함 .. 2개 곱하기
    //}

    //5. 효율적인 화폐 구성
    //int n, m;
    //vector<int> arr;
    //cin >> n >> m;
    //for (int i = 0; i < n; i++) {
    //    int x;
    //    cin >> x;
    //    arr.push_back(x);
    //}
    //
    //vector<int> d(m + 1, 10001);
    //
    //d[0] = 0;
    //for (int i = 0; i < n; i++) {
    //    for (int j = arr[i]; j <= m; j++) { //각 화폐의 단위
    //        if (d[j - arr[i]] != 10001) {
    //            d[j] = min(d[j], d[j - arr[i]] + 1); // d[j] : 금액 j를 만들수 있는 최소한의 화폐 개수
    //                                                 // d[j - arr[i]] + 1 : 화폐 하나 추가하기
    //        }
    //    }
    //}
    //if (d[m] == 10001)
    //    cout << -1;
    //else
    //    cout << d[m];
}