다이나믹 프로그래밍 솔루션:: 백준 11051, 9251, 1520

1. 문제 10051

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

 

1) 주의해야 할 점

모듈러 계산에서는 나눗셈을 정의하지 않기 때문에

팩토리얼을 통한 조합 계산이 문제 조건상 허용되지 않는다.

그렇기에 파스칼 삼각형을 이용해서 풀어야 한다.

 

2) 탑-다운 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 10'007

int N, K;

vector<vector<int>> dp;

int Combine(int n, int k)
{
if (dp[n][k] != -1)
return dp[n][k];

if (k == 0 || n == 0 || k == n)
return dp[n][k] = 1;

if (k == 1)
return dp[n][k] = n;

return dp[n][k] = (Combine(n - 1, k - 1) + Combine(n - 1, k)) % MAX;
}

int main()
{
cin >> N >> K;

dp.resize(N+1, vector<int>(N + 1, -1));

cout << Combine(N, K);
return 0;
}

3) 바텀-업 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 10'007

int N, K;

vector<vector<int>> dp;

int main()
{
cin >> N >> K;

dp.resize(N+1, vector<int>(N + 1, 1));

for(int i=2;i<=N;i++)
for (int j = 1; j < i; j++)
dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % MAX;

cout << dp[N][K];

return 0;
}

 

 

2. 문제 10051

1. 주의해야 할 점

분할정복적 사고가 핵심인 문제

2차원 표를 만들어서 고민해보면 푸는데 도움이 된다.

 

2. 탑-다운 방식

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 10'007

int N, K;
string str1, str2;
vector<vector<int>> dp;

int Solution(int x, int y)
{
if (x == -1 || y == -1)
return  0;

if (dp[x][y] != -1)
return dp[x][y];

if (str1[x] == str2[y])
return dp[x][y] = Solution(x - 1, y - 1) + 1;

return dp[x][y] = max(Solution(x - 1, y), Solution(x, y - 1));
}

int main()
{
cin >> str1 >> str2;

str1 = str1;
str2 = str2;

dp.resize(str1.size() + 1, vector<int>(str2.size() + 1, -1));

cout << Solution(str1.size()-1, str2.size() - 1);

return 0;
}

 

3. 바텀-업 방식

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 10'007

int N, K;
string str1, str2;
vector<vector<int>> dp;

int main()
{
cin >> str1 >> str2;

str1 = " " + str1;
str2 = " " + str2;

dp.resize(str1.size() + 1, vector<int>(str2.size() + 1, 0));

for (int i = 1; i < str1.size(); i++)
{
for (int j = 1; j < str2.size(); j++)
{
if (str1[i] == str2[j])
{
dp[i][j] = dp[i - 1][j-1] + 1;
}
else
{
dp[i][j] = max(dp[i-1][j], dp[i][j - 1]);
}
}
}

auto it = *max_element(dp.begin(), dp.end());


cout << *max_element(it.begin(), it.end());

return 0;
}

 

3. 문제 1520

1. 주의해야 할 점

전수조사를 해야하는 문제이기 때문에 BFS 탐색으로는 풀기 어려운 문제다.

그렇기에 DFS를 사용하는 것이 문제푸는데 도움이 될 것이고,

DFS 특성상 stack으로 구현하는 것 보다는 재귀로 구현하는 것이 훨씬 깔끔하다.

 

처음 문제를 만났을 때 과연 이 문제에서 DP를 어떻게 활용할까에 대한 고민을 길게했다.

이 문제는 어디서 중복되는 계산이 발생하는지 인지하는 것이 핵심인 문제이다.

 

2. 탑-다운 방식 방식

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

int table[501][501];
int visited[501][501];
int dp[501][501];
int M, N;

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int Solution(int y, int x)
{
if (y == M - 1 && x == N - 1)
return 1;

if (visited[y][x])
return dp[y][x];

visited[y][x] = true;

for (int dir = 0; dir < 4; dir++)
{
int nX = x + dx[dir];
int nY = y + dy[dir];

if (nY < 0 || nX < 0 || nY >= M || nX >= N)
continue;

if (table[nY][nX] >= table[y][x])
continue;

dp[y][x] = dp[y][x] + Solution(nY, nX);
}

return dp[y][x];
}

int main()
{
cin >> M >> N;

for(int i=0;i<M;i++)
for (int j = 0; j < N; j++)
cin >> table[i][j];

cout << Solution(0, 0);

return 0;
}