728x90
https://www.acmicpc.net/problem/1463
가장 기초적인 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
#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
#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은 본격적으로 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
#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
이 문제는 엄청 좋은 문제인 이유가
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;
}
728x90
'알고리즘, PS, 문제풀기등 > 5) 패러다임(백트래킹, DP, 분할 정복, 분기, 그리디, 최소 신장)' 카테고리의 다른 글
BF(일반) - 기초(1) (0) | 2023.01.03 |
---|