동적 계획법 기초

1932번 문제 : 피보나치 함수

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

#include <iostream>
using namespace std;
 
struct MyFibo
{
    int value;
    int zeroCount;
    int oneCount;
};
 
MyFibo fib[50];
int GetFibo(int n)
{
    if (n == 0)
    {
        fib[0].value = 0;
        fib[0].zeroCount = 1;
        return 0;
    }
 
    else if (n == 1)
    {
        fib[1].value = 1;
        fib[1].oneCount = 1;
        return 1;
    }
    
    if (fib[n].value != 0)
    {
        return fib[n].value;
    }
    else
    {
        fib[n].value = GetFibo(n - 1) + GetFibo(n - 2);
        fib[n].zeroCount = fib[n - 1].zeroCount + fib[n - 2].zeroCount;
        fib[n].oneCount = fib[n - 1].oneCount + fib[n - 2].oneCount;
    }
}
 
int main() {
    int inp;
    cin >> inp;
 
    while (inp > 0)
    {
        int a;
        cin >> a;
        zeroCounter = 0;
        oneCounter = 0;
        GetFibo(a);
        cout << fib[a].zeroCount << " " << fib[a].oneCount << endl;
 
        inp--;
    }
 
    return 0;
}

1149번 문제 : RGB거리

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

#include <iostream>
#include <algorithm>  
using namespace std;
 
int DP[1001][4] = { 0 };
 
int main() {
    int inp;
    cin >> inp;
 
    for (int i = 1; i <= inp; i++)
    {
        int r, g, b;
        cin >> r >> g >> b;
 
        DP[i][1] = r;
        DP[i][2] = g;
        DP[i][3] = b;
    }
 
    for (int i = 2; i <= inp; i++)
    {
        for (int j = 1; j <= 3; j++)
        {
            if (j == 1)
                DP[i][j] += min(DP[i - 1][2], DP[i - 1][3]);
            else if (j == 2)
                DP[i][j] += min(DP[i - 1][1], DP[i - 1][3]);
            else if (j == 3)
                DP[i][j] += min(DP[i - 1][1], DP[i - 1][2]);
        }
    }
 
    int min = DP[inp][1];
    for (int j = 1; j <= 3; j++)
    {
        if (DP[inp][j] < min)
            min = DP[inp][j];
    }
 
    cout << min << endl;
 
 
    return 0;
}

1932번 문제 : 정수 삼각형

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

#include <iostream>
#include <algorithm>
using namespace std;
 
int DP[501][501] = { 0 };
 
int main()
{
    int size;
    cin >> size;
    for (int i = 1; i <= size; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            int inp;
            cin >> inp;
            DP[i][j] = inp;
        }
    }
 
    for (int i = 2; i <= size; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            if (j == 1)
            {
                DP[i][j] += DP[i - 1][j];
            }
            else if (j == i)
            {
                DP[i][j] += DP[i - 1][j - 1];
            }
            else
            {
                DP[i][j] += max(DP[i - 1][j - 1], DP[i - 1][j]);
            }
        }
    }
 
    int max = 0;
    for (int j = 1; j <= size; j++)
    {
        if (DP[size][j] > max)
            max = DP[size][j];
    }
 
    cout << max << endl;
 
    return 0;
}
 

메모:

-위쪽부터 누적 최대값을 취하는 방식으로 풀어야함

-양쪽끝 (위 코드에서는 j =1 또는 j =i)일때는 받을 수 있는 값은 하나 밖에 없음

-가운데에 있는 숫자들은 양쪽에서 값을 받을 수 있음

1463번 문제 : 1로 만들기

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int arr[1000001] = { 0 };
 
int GetValue(int num)
{
    if (num == 0 || num == 1)
    {
        arr[num] = 0;
        return 0;
    }
    else if (num == 2 || num == 3)
    {
        arr[num] = 1;
        return 1;
    }
 
    if (arr[num] != 0)
        return arr[num];
    else
    {
        arr[num] = arr[num - 1] + 1;
 
        if (num % 2 == 0)
        {
            arr[num] = min(arr[num], arr[num / 2] + 1);
        }
 
        if (num % 3 == 0)
        {
            arr[num] = min(arr[num], arr[num / 3] + 1);
        }
        
 
        return arr[num];
    }
}
 
int main()
{
    int inp;
    cin >> inp;
 
    for (int i = 1; i <= inp; i++)
    {
        GetValue(i);
    }
 
    cout << arr[inp] << endl;
 
    return 0;
}

메모:

-3부터 나뉘어지면 무조건 취소값이라고 생각하면 안됨

-그래서 그 전의 수와 비교하면서 루프를 돌아야함

9461번 문제 : 파도반 수열

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

#include <iostream>
#include <vector>
using namespace std;
 
signed long long value[101] = { 0,1,1,1,2,2,3,4,5,7 };
vector<signed long long> result;
 
int GetValue(int num)
{
    if (num <= 8)
        return value[num];
    else
    {
        if (value[num] != 0)
            return value[num];
        else
        {
            value[num] = value[num - 1] + value[num - 5];
            return value[num];
        }
    }
}
 
 
int main() {
    
    int t;
    cin >> t;
 
    for (int i = 0; i <= 100; i++)
    {
        GetValue(i);
    }
 
    while (t > 0)
    {
        int inp;
        cin >> inp;
 
        result.push_back(value[inp]);
 
        t--;
    }
 
    for (auto i : result)
        cout << i << endl;
 
 
    return 0;
}

메모:

-i가 80정도 이상이면 long long 범위를 벗어나 답을 못구함...