오늘은 DP 태그에서 내가 안 푼 문제 중 푼 사람 수가 많은 문제들을 풀 것이다.
DP나 그리디는 같은 골드 난이도 문제들 중에서도 새로운 아이디어를 떠올려야 하는 경우가 많아서 일정 시간 내에 풀이가 떠오르지 않는다면 풀이를 참고하여 푸는 문제가 꽤 있을 수도 있다.
백준 BOJ 2011번 : 암호코드
문제 난이도 : Gold V
알고리즘 분류 : DP
이 문제는 다른 풀이도 확인해보았으나 설명이 부족한 글이 많아서 내가 신경써서 정리했으므로 맨 위에 배치한다. (!!)
숫자로만 이루어진 문자열을 각 숫자가 알파벳 번호라고 생각하고 해독할 때 해독할 수 있는 서로 다른 알파벳 문자열의 수를 구하는 문제이다.
(예를 들면 25는 B와 E로 해석할 수도 있지만 25번째 알파벳 Y로 해석할 수도 있다.)
각 자리에 대해 검사해야되는 것은 두 가지이다.
1. 이 숫자 하나가 하나의 알파벳이 될 수 있는가? (1 ~ 9이면 A ~ I로 해독이 된다. 0만 아니면 됨.)
2. 앞 자리 숫자와 이 숫자가 합쳐져서 하나의 알파벳이 될 수 있는가? (09는 그냥 9와 다르므로 앞자리가 0인 것은 안 되고, 앞 자리가 1이거나, 앞 자리가 2이면서 현재 자리가 0 ~ 6이면 된다.)
dp로 풀이하기 위해 먼저 dp 벡터를 선언해준다.
dp[i+1]는 문자열의 i번째 자리까지 해독하는 방법의 수라고 두자.
뒤로 넘어가면서 만약 현재 숫자가 0이 아니라면, 즉 1 ~ 9 자체만으로 하나의 알파벳이 된다면 dp[i]를 dp[i+1]에 더해준다.
왜냐하면 이 경우의 수는 앞자리까지 해독하는 경우의 수와 일대일 대응이 되기 때문이다. (현재 자리 숫자가 없다고 생각해보자. 일대일 대응이 된다.)
앞 자리 숫자를 포함하여 두 자리 숫자가 10 ~ 26이라면 현재 자리를 앞 자리랑 묶어서 세는 경우의 수는, 두 칸 앞자리까지 해독하는 경우의 수와 일대일 대응이 되기 때문에 (왜냐하면 앞자리랑 두 자리를 묶어서 하나의 수가 되었기 때문에 이 두 자리 수를 제거한다고 생각해보자. 일대일 대응이 된다.) dp[i-1]를 dp[i+1]에 더해주면 된다.
최종적으로 i는 str.length()-1까지 탐색하므로, 우리가 찾는 답은 dp[str.length()]에 구해진다.
따라서 이를 답으로 출력해주면 된다.
예외로는 문자열 자체가 0으로 시작하는 경우가 있다. 이 경우는 답으로 1이 얻어져야 하지만 dp의 정의에 따라 0이 출력되니 예외 처리를 해주자.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
string str; cin >> str;
if(str[0] == '0') {
cout << 0 << "\n";
return 0;
}
vector<int> dp(str.length()+1);
dp[0] = 1, dp[1] = 1;
for(int i=1; i<str.length(); i++) {
if(str[i] != '0') dp[i+1] += dp[i];
if(i > 0 && (str[i-1] == '1' || (str[i-1] == '2' && str[i] <= '6'))) dp[i+1] += dp[i-1];
dp[i+1] %= (int)(1e6);
}
cout << dp[str.length()] << "\n";
}
백준 BOJ 1562번 : 계단 수
문제 난이도 : Gold I
알고리즘 분류 : 비트필드를 이용한 DP
인접한 자리수의 숫자가 1씩 차이나는 수를 계단 수라고 할 때, 길이가 N이면서 0~9가 모두 한 번 이상 나오는 계단 수의 개수를 구하는 문제이다. (이 때 0으로 시작하는 수는 제외해야 한다.)
일반적인 계단 수라면 dp[i][j]를 j로 끝나는 길이가 i인 계단 수의 개수로 놓고 점화식을 세워서 간단히 풀이할 수 있지만, 이 문제에서는 0~9가 나왔는지를 체크해야한다.
0~9는 10개의 숫자이고 각각이 나오고 안 나옴을 모두 체크해봐도 2^10의 경우의 수이다.
따라서 벡터에 차원을 한 차원 증가시켜 3차원 벡터 + 비트필드를 이용하여 DP로 풀 수 있다.
예를 들어 dp[i][j][(0000001111)2]는 길이가 i이고 j로 끝나며, 0, 1, 2, 3이 한 번 이상 등장한 계단 수의 개수이다.
점화식을 세워보면 길이가 i이고 j로 끝나는 계단 수의 개수에 길이가 i-1이고 j-1 또는 j+1로 끝나는 계단 수의 개수를 더해주되, 이번 수에서 j가 나타남을 체크하기 위해 k에 (1 << j) 값을 or 연산하여 중첩시켜주면 된다.
3차원 벡터이므로 k에 대해서도 1 ~ (1 << 10) - 1 사이에 대해 반복문을 돌려주어야 모두 기록이 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<vector<vector<int>>> dp(N+1, vector<vector<int>>(10, vector<int>(1 << 10)));
for(int i=1; i<=9; i++) dp[1][i][1 << i] = 1;
for(int i=2; i<=N; i++)
for(int j=0; j<=9; j++)
for(int k=1; k<(1 << 10); k++) {
if(j == 0) dp[i][j][k | (1 << j)] += dp[i-1][j+1][k];
else if(j == 9) dp[i][j][k | (1 << j)] += dp[i-1][j-1][k];
else dp[i][j][k | (1 << j)] += dp[i-1][j-1][k] + dp[i-1][j+1][k];
dp[i][j][k | (1 << j)] %= (int)(1e9);
}
int ans = 0;
for(int i=0; i<=9; i++) ans += dp[N][i][(1 << 10) - 1];
ans %= (int)(1e9);
cout << ans << "\n";
}
백준 BOJ 1937번 : 욕심쟁이 판다
문제 난이도 : Gold III
알고리즘 분류 : DFS + DP
어떤 지점에서 시작하여 상하좌우로 이동하여 더 큰 수로 이동할 때, 최대한 많은 칸을 방문할 때 그 칸의 수를 구하는 문제이다.
먼저 모든 칸에 대해 시작점을 잡고 탐색하는 것은 불가피해보인다.
따라서 2중 for문으로 모든 칸에서 출발하는 탐색을 구현하면 된다.
이것은 DFS와 비슷한 방식으로 구현이 가능하며, 여기에 DP를 활용하여 풀이할 수 있다.
만약 이동 중 해당 칸의 DP 값이 0보다 크다면, 더 탐색을 할 필요없이 그 칸의 DP 값을 가져와서 더해주면 되기 때문이다. (그 칸에서 시작해서 이동 가능한 최대값이므로 다른 칸에서 그 칸을 방문할 수 있다면 다른 칸의 DP 값에 그 칸의 DP 값을 더해주면 된다.)
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N;
vector<vector<int>> v, dp;
int f(int x, int y) {
if(dp[x][y] > 0) return dp[x][y];
dp[x][y] = 1;
int Max = 0;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
for(int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
if(v[nx][ny] <= v[x][y]) continue;
Max = max(Max, f(nx, ny));
}
return dp[x][y] = dp[x][y] + Max;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> N;
v.resize(N, vector<int>(N));
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) cin >> v[i][j];
int ans = 0;
dp.resize(N, vector<int>(N));
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) ans = max(ans, f(i, j));
cout << ans << "\n";
}
백준 BOJ 1915번 : 가장 큰 정사각형
문제 난이도 : Gold IV
알고리즘 분류 : DP
0과 1로 이루어진 2차원 배열이 주어졌을 때, 1로만 이루어진 가장 큰 정사각형의 넓이를 구하는 문제이다.
DP를 이용하여 해결할 수 있는 문제이다.
왼쪽 위부터 오른쪽 아래로 탐색하면서 내려간다고 생각해보자.
그러면 어떤 칸에 대해서 왼쪽, 위쪽, 왼쪽 위 칸 3개가 모두 1이면 정사각형의 크기를 갱신해줄 수 있다.
(이것은 수학적 귀납법을 떠올리면 된다. 이미 탐색한 왼쪽, 위쪽, 왼쪽 위 칸들에 대해서도 같은 방식으로 스캔을 해줬을 것이니 dp에 짧은 쪽 변의 길이를 저장해두면 정사각형의 크기를 알 수 있게 된다.)
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<vector<char>> v(N, vector<char>(M));
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) cin >> v[i][j];
vector<vector<int>> dp(N, vector<int>(M));
int ans = 0;
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) {
if(i == 0 || j == 0) dp[i][j] = v[i][j] - '0';
else if(v[i][j] == '1')
dp[i][j] = min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]}) + v[i][j] - '0';
ans = max(ans, dp[i][j] * dp[i][j]);
}
cout << ans << "\n";
}
백준 BOJ 2096번 : 내려가기
문제 난이도 : Gold V
알고리즘 분류 : DP
맨 윗줄에서 시작하여 왼쪽 아래, 아래, 오른쪽 아래 칸 중 하나로 내려갈 때 지나간 칸들의 합의 최댓값과 최솟값을 구하는 문제이다.
이 문제의 핵심은 메모리 제한에 있는데, 메모리 제한이 4MB밖에 되지 않으므로 2차원 배열을 사용한 DP 풀이는 불가능하다.
따라서 각 줄마다 이전 최댓값과 현재 갱신할 최댓값 배열 3칸짜리를 가지고 값을 계속 옮겨주는 방식으로 풀이해야한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
int cmax[3] = {}, cmin[3] = {}, pmax[3] = {}, pmin[3] = {};
for(int i=0; i<N; i++) {
int a, b, c; cin >> a >> b >> c;
cmax[0] = a + max(pmax[0], pmax[1]);
cmin[0] = a + min(pmin[0], pmin[1]);
cmax[1] = b + max({pmax[0], pmax[1], pmax[2]});
cmin[1] = b + min({pmin[0], pmin[1], pmin[2]});
cmax[2] = c + max(pmax[1], pmax[2]);
cmin[2] = c + min(pmin[1], pmin[2]);
for(int j=0; j<3; j++) {
pmax[j] = cmax[j];
pmin[j] = cmin[j];
}
}
int Max = max({pmax[0], pmax[1], pmax[2]});
int Min = min({pmin[0], pmin[1], pmin[2]});
cout << Max << " " << Min << "\n";
}
백준 BOJ 5557번 : 1학년
문제 난이도 : Gold V
알고리즘 분류 : DP
첫 번째 수를 제외한 나머지 수들에 + 또는 -의 부호를 적용시켜 연산을 했을 때 맨 오른쪽 수가 얻어지는 경우의 수를 구하는 문제이다.
당연히도 제한 조건이 있는데 각 연산 중간에 0 미만 20 초과의 값이 나올 수 없다.
중간마다 0 ~ 20의 값이 나오는 경우의 수를 배열에 저장하여 뒤로 넘어가면서 앞의 값들을 참조하여 계산하면 된다.
주의할 점은 맨 앞의 부호는 +로 고정되어야 한다.
일반적으로는 반례가 나올 수 없지만, 2 0 0이 입력으로 들어오는 경우 원래는 0 = 0으로 답이 1이지만, 맨 앞 수의 부호를 고정하지 않으면 +0과 -0을 다르게 고려하여 2라는 잘못된 답이 나온다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v(N+1);
for(int i=1; i<=N; i++) cin >> v[i];
vector<vector<int>> dp(N+1, vector<int>(21));
dp[1][v[1]] = 1;
for(int i=2; i<N; i++) {
for(int j=0; j<=20; j++) {
if(j + v[i] <= 20) dp[i][j + v[i]] += dp[i-1][j];
if(j - v[i] >= 0) dp[i][j - v[i]] += dp[i-1][j];
}
}
cout << dp[N-1][v[N]] << "\n";
}
백준 BOJ 5582번 : 공통 부분 문자열
문제 난이도 : Gold V
알고리즘 분류 : DP, 문자열
두 문자열의 가장 긴 공통 부분 문자열의 길이를 구하는 문제이다.
공통 부분 문자열 자체를 구하는 문제도 아니고, 문자열의 길이도 4,000 이하라서 O(N^2)에도 충분히 돌아간다.
이중 for문을 활용하여 만약 a[i]와 b[j]가 같다면 a[i-1]과 b[j-1]에 저장되어 있는 최장 길이에 1을 더해주면 되고, 그렇지 않은 경우 공통 부분 문자열이 끊기므로 기존에 초기화 되어있는 값인 0을 그대로 두고 넘어가면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
string a, b; cin >> a >> b;
vector<vector<int>> dp(a.length()+1, vector<int>(b.length()+1));
int ans = 0;
for(int i=0; i<a.length(); i++)
for(int j=0; j<b.length(); j++) {
if(a[i] != b[j]) continue;
dp[i+1][j+1] = dp[i][j] + 1;
ans = max(ans, dp[i+1][j+1]);
}
cout << ans << "\n";
}
백준 BOJ 2631번 : 줄세우기
문제 난이도 : Gold IV
알고리즘 분류 : DP (LIS)
N개의 수가 있을 때, 정렬하기 위해서 옮겨야 하는 수의 개수를 구하는 문제이다.
LIS(가장 긴 증가하는 부분 수열)의 크기를 구하고 이 LIS에 포함되지 않는 수들만 옮기면 된다.
O(N^2) 시간에 풀이해도 되지만, 내가 이전에 잘 정리해둔 O(N log N) 코드가 있어서 이를 활용했다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
vector<int> u;
u.push_back(v[0]);
int cnt = 0;
vector<pair<int, int>> dp(N);
dp[0] = {v[0], 0};
for(int i=1; i<N; i++) {
if(v[i] > u.back()) {
u.push_back(v[i]);
cnt++;
dp[i] = {v[i], cnt};
}
else {
int x = lower_bound(u.begin(), u.end(), v[i]) - u.begin();
u[x] = v[i];
dp[i] = {v[i], x};
}
}
cout << N - (cnt + 1) << "\n";
}
백준 BOJ 1238번 : 파티
문제 난이도 : Gold III
알고리즘 분류 : 데이크스트라 (다익스트라)
단방향 연결 그래프가 주어졌을 때, 특정 노드를 기준으로 왕복 거리가 가장 먼 노드의 거리를 구하는 문제이다.
이 문제는 DP 문제는 아니지만 지나가다가 보여서 그냥 풀었다.
단방향 연결 그래프이므로, 두 노드를 왕복하는 거리가 다를 수 있다.
또한 모든 노드에 대해 다르게 출발점을 잡고 거리를 구하면 시간 초과가 발생한다.
출발점에서 다른 모든 노드에 도달하는 시간은 기존 다익스트라 코드와 같다.
문제가 되는 부분인 모든 노드에서 출발점으로 오는 경로는 시간을 줄일 방법을 생각해야 한다.
해결책은 간선을 반대로 연결한 그래프 하나를 따로 만들어서 출발점으로부터 모든 노드에 도달하는 거리를 데이크스트라로 구해주는 것이다.
간선을 반대로 연결했기 때문에 출발점에서 어떤 노드에 도달하는 거리는, 원래 그래프에서 어떤 노드에서 출발점으로 도달하는 거리와 같아진다.
이제 두 그래프에서 구한 각 거리의 합 중 최댓값을 답으로 얻어주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> p;
vector<vector<p>> adj, adjr;
vector<int> dis, disr;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M, K; cin >> N >> M >> K;
adj.resize(N+1);
adjr.resize(N+1);
while(M--) {
int a, b, c; cin >> a >> b >> c;
adj[a].push_back({b, c});
adjr[b].push_back({a, c});
}
dis.resize(N+1, INT_MAX);
dis[K] = 0;
priority_queue<p, vector<p>, greater<p>> pq; // <dis, node>
pq.push({0, K});
while(!pq.empty()) {
int dis1 = pq.top().first;
int cur = pq.top().second;
pq.pop();
if(dis[cur] < dis1) continue;
for(int i=0; i<adj[cur].size(); i++) {
int nex = adj[cur][i].first;
int dis2 = adj[cur][i].second;
if(dis1 + dis2 < dis[nex]) {
dis[nex] = dis1 + dis2;
pq.push({dis[nex], nex});
}
}
}
disr.resize(N+1, INT_MAX);
disr[K] = 0;
pq.push({0, K});
while(!pq.empty()) {
int dis1 = pq.top().first;
int cur = pq.top().second;
pq.pop();
if(disr[cur] < dis1) continue;
for(int i=0; i<adjr[cur].size(); i++) {
int nex = adjr[cur][i].first;
int dis2 = adjr[cur][i].second;
if(dis1 + dis2 < disr[nex]) {
disr[nex] = dis1 + dis2;
pq.push({disr[nex], nex});
}
}
}
int ans = 0;
for(int i=1; i<=N; i++) ans = max(ans, dis[i] + disr[i]);
cout << ans << "\n";
}
백준 BOJ 17070번 : 파이프 옮기기 1
문제 난이도 : Gold V
알고리즘 분류 : DP
가로로 1칸, 세로로 1칸, 대각선(오른쪽 아래)으로 1칸으로 구성된 파이프들을 적절히 연결해서 1행 2열에서 N행 N열로 도달하는 경우의 수를 구하는 문제이다.
먼저 가로로 1칸짜리인 파이프 하나가 연결된 상태로 시작하기 때문에 1행 2열에서부터 시작함에 유의하자.
DP와 재귀 함수를 이용하여 연결 가능한 파이프를 연결하여 다음 함수를 호출하다가, N행 N열에 도달하는 경우 답에 1을 더해서 리턴하는 방식으로 풀이할 수 있다.
일반적인 DFS와 비슷한 방식으로 풀이가 가능하나, 대각선 파이프를 연결하는 경우 (x+1, y)와 (x, y+1) 좌표에 아무것도 없는지 체크를 해주어야 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N, ans = 0;
vector<vector<int>> v;
void f(int x, int y, int dir) {
if(x == N-1 && y == N-1) {
ans++;
return;
}
int dx[3] = {1, 0, 1};
int dy[3] = {0, 1, 1};
for(int i=0; i<3; i++) {
if(dir == 0 && i == 1) continue;
if(dir == 1 && i == 0) continue;
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= N || ny >= N) continue;
if(v[nx][ny] == 1) continue;
if(i == 2 && (v[x+1][y] == 1 || v[x][y+1] == 1)) continue;
f(nx, ny, i);
}
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> N;
v.resize(N, vector<int>(N));
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) cin >> v[i][j];
f(0, 1, 1);
cout << ans << "\n";
}
'알고리즘 > 알고리즘 공부 내용 정리' 카테고리의 다른 글
| 백준 BOJ Gold 난이도 구현 외 다양한 문제들 풀이 220812 (0) | 2022.08.12 |
|---|---|
| 백준 BOJ 구현, 시뮬레이션 문제 위주 풀이 모음 220811 (0) | 2022.08.11 |
| 백준 BOJ 풀이 : Disjoint set, 유니온 파인드 문제들 풀이 220809 (0) | 2022.08.09 |
| 백준 BOJ 문제 풀이 모음 220804 (0) | 2022.08.04 |
| 백준 BOJ 브론즈 ~ 실버 기하 문제들 풀이 모음 등 220803 (0) | 2022.08.03 |