문제
https://www.acmicpc.net/problem/14722
풀이
이 문제를 처음 봤을 때 입력 크기가 그렇게 크지 않아서 완탐 문제인 줄 알았다. 가능한 모든 경우의 수 중에서 최댓값을 출력하려고 했는데, 풀다가 막혀서 답을 봤더니 dp로 풀어야 시간초과가 나지 않는다고 한다.
평범한 그래프 탐색 문제와 다르게, 이 문제는 동남쪽으로 이동할 때마다 우유를 마실 수 있는 게 아니다!
딸기 -> 바나나 -> 초코 반드시 이 순서를 지키면서 우유를 마셔야 한다. 그렇지 않으면 우유를 마시지 않은 상태에서 다른 도시로 이동해야 한다.
예를 들어 (0, 0) 위치에서 우유를 마시고 계속 안 마시다가 (3, 3) 위치에서 마실 수도 있다. 따라서 단순히 이전 칸의 우유를 확인하는 게 아니라, 이전 칸에서 어떤 우유를 마신 상태인지 알아야 한다. 이를 위해 3차원 dp 테이블이 필요하다.
📌 dp[k][i][j] : (i, j) 위치에 도달할 때까지 가장 최근에 마신 우유가 k일 때, 최대로 마신 우유의 개수
(i) 우유를 마실 수 있는 경우
언제 우유를 마실 수 있는지 생각해보자.
우유 도시가 다음과 같다면 2번 우유를 마실 수 "없다". 왜냐하면 2번의 이전 칸이 1이지만, 0번 우유를 마신 적이 없어서 1번 우유 또한 마실 수 없기 때문이다.
1 1
1 2
반면에 다음과 같은 경우에는 2번 우유를 마실 수 "있다". 이전 칸이 1인 것은 동일하지만, 바로 그 이전 칸에서 0번 우유 또한 마실 수 있기 때문이다.
0 1
1 2
이를 종합해보면 다음과 같다.
dp[이전 우유 번호][이전 칸][이전 칸] == 0: 이전 칸의 우유를 마실 수 없는 경우dp[이전 우유 번호][이전 칸][이전 칸] > 0: 이전 칸의 우유를 마실 수 있는 경우
(ii) 우유를 마실 수 없는 경우
현재 칸에서 우유를 마실 수 없는 경우에는, 이전 칸과 현재 칸의 dp 값 중에서 최댓값을 저장한다.
그리고 0번 우유는 (마시는 순서의 출발점이어서) 앞의 우유를 하나도 마시지 않으면 무조건 마실 수 있기 때문에 dp[0][0번 우유 r][0번 우유 c] = 1 로 초기화 한다.
C++ 코드
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 1001;
int milk[MAX][MAX];
int dp[3][MAX][MAX];
int N;
// 이전 방향: 0(왼쪽), 1(위쪽)
int dx[] = {0, -1};
int dy[] = {-1, 0};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
cin >> milk[i][j];
if(milk[i][j] == 0) {
dp[0][i][j] = 1;
}
}
}
for(int x = 0; x < N; x++){
for(int y = 0; y < N; y++){
for(int d = 0; d < 2; d++){
int px = x + dx[d]; // 이전 x
int py = y + dy[d]; // 이전 y
if(px < 0 || px >= N || py < 0 || py >= N) continue;
int curMilk = milk[x][y];
int prevMilk = (curMilk + 2) % 3;
// 우유를 마실 수 없는 경우
dp[0][x][y] = max(dp[0][x][y], dp[0][px][py]);
dp[1][x][y] = max(dp[1][x][y], dp[1][px][py]);
dp[2][x][y] = max(dp[2][x][y], dp[2][px][py]);
// 우유를 마실 수 있는 경우
if(dp[prevMilk][px][py] > 0) {
dp[curMilk][x][y] =
max(dp[curMilk][x][y], dp[prevMilk][px][py] + 1);
}
}
}
}
int ans = max(max(dp[0][N - 1][N - 1], dp[1][N - 1][N - 1]), dp[2][N - 1][N - 1]);
cout << ans;
return 0;
}이전 칸에서 어떤 우유를 마셨는지에 따라 현재 마실 우유의 종류가 결정되기 때문에, 다음 칸이 아니라 '이전' 칸의 상태를 살펴봐야 한다.
어렵다.. 이런 유형의 문제는 처음이다! dp랑 그래프 탐색을 합쳐놓으니까 더 까다로웠다.
참고자료
