DP - 기초(1)

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

1463번: 1로 만들기

가장 기초적인 1로 만들기 문제이다.

DP의 탑 다운 방식으로 생각해서 문제를 풀 수 있다는 장점이 있다.

 

패러다임 관련 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#define ll long long
using namespace std;

int d[1000001];
int main(void)
{
//    freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin>>n;
    d[2] = 1;
    for(int i = 3 ; i <= n ; ++i)
    {
        d[i] = d[i - 1] + 1;
        if (i % 2 == 0 && d[i] > d[i/2] + 1) d[i] = d[i/2] +1;
        if (i % 3 == 0 && d[i] > d[i/3] + 1) d[i] = d[i/3] + 1;
    }
    cout<<d[n]<<'\n';
}

 

 

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

11727번: 2×n 타일링 2

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#define ll long long
using namespace std;

int d[1001];
int main(void)
{
    //freopen("input.txt", "r", stdin);
    // ios_base::sync_with_stdio(false);
    // cin.tie(nullptr);
    // cout.tie(nullptr);

    int n;
    scanf("%d\n", &n);
    d[1] = 1;
    d[2] = 3;
    if (n>=3)
    {
        for(int i = 3; i <= n ; ++i)
        {
            d[i] = (d[i-1] + d[i-2] *2)%10007;
        }
    }
    printf("%d\n",d[n]);
}

 

 

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

9095번: 1, 2, 3 더하기

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#define ll long long
using namespace std;

int d[12];
int main(void)
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    cin >> t;

    d[1] = 1;
    d[2] = 2;
    d[3] = 4;
    for(int i = 4; i <= 11 ; i++)
    {
        d[i] = d[i-1] + d[i-2] + d[i-3];
    }

    while(t--)
    {
        int tmp;
        cin>>tmp;
        cout<<d[tmp]<<'\n';
    }
    return 0;
}

 

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

15990번: 1, 2, 3 더하기 5

15990은 본격적으로 2차원 DP를 사용하는 예시 문제이다.

 

바로 이전에 나온 숫자가 나와 겹치지 않게 조건문을 넣어주어야 한다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#define ll long long
using namespace std;

vector<vector<long long> > d(100001, vector<long long>(4));
long long mod = 1000000009;
int main(void)
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    cin >> t;
    d[1][1] = d[2][2] = d[3][1] = d[3][2] = d[3][3] = 1;
    for(int i = 4; i<=100000;++i)
    {
        d[i][1] = (d[i-1][2] + d[i-1][3])%mod;
        d[i][2] = (d[i-2][1] + d[i-2][3])%mod;
        d[i][3] = (d[i-3][1] + d[i-3][2])%mod;
    }
    while(t--)
    {
        int n;
        cin>>n;
        cout<<(d[n][1]+d[n][2]+d[n][3])%mod<<'\n';
    }
    return 0;
}

 

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

10844번: 쉬운 계단 수

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#define ll long long
using namespace std;

vector<vector<long long> > d(101, vector<long long> (10));
long long mod = 1000000000;
int main(void)
{
    freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin>>n;
    d[1][1]=d[1][2]=d[1][3]=d[1][4]=d[1][5]=d[1][6]=d[1][7]=d[1][8]=d[1][9] = 1;
    for(int i = 2; i<=n;++i)
    {
        for(int j=0; j<=9;++j)
        {
            if(j == 0)
                d[i][j] = (d[i-1][1])%mod;
            else if(j == 9)
                d[i][j] = (d[i-1][8])%mod;
            else
                d[i][j] = (d[i-1][j-1]+d[i-1][j+1])%mod;
        }
    }
    long long ans =0;
    for(int i = 0 ; i<=9;++i)
    {
        ans=(ans+d[n][i])%mod;
    }
    cout<<ans<<'\n';
    return 0;
}

이와 유사하게 쉬운 계단수 문제도 2차원 DP 문제가 된다. 조건이 붙은 순간부터 DP는 배열이 하나씩 늘어난다고 볼 수 있다.

 

 

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

11053번: 가장 긴 증가하는 부분 수열

이 문제는 엄청 좋은 문제인 이유가

DP인 동시에 lower bound 가 되기 때문이다.

 

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

vector<int> d;
int main(void) {
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int		t;
	cin >> t;
	while (t--)
	{
		int		temp;
		cin >> temp;
		auto it = lower_bound(d.begin(), d.end(), temp);
		if (it == d.end())
		{
			d.push_back(temp);
		}
		else {
			*it = temp;
		}
	}
	cout << d.size() << '\n';
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;

vector<int> d(1001,1);
int main(void)
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin>>n;
    vector<int> a(1001);
    for(int i = 0 ; i < n ; ++i)
    {
        cin>>a[i];
    }
    d[0] = 1;
    for(int i = 1 ; i < n ; ++i)
    {
        for(int j = 0 ; j <i ; ++j )
        {
            if (a[j] < a[i] && d[j] + 1 > d[i] )
                d[i] = d[j] + 1;
        }
    }
    cout<<*max_element(d.begin(), d.end())<<'\n';

    return 0;
}