안녕하세요,
재재입니다.
BOJ 2873 롤러코스터 문제 풀이입니다.
BOJ 2873 롤러코스터
(1) 문제 설명
분류 : bruteforce, greedy
출처 : https://www.acmicpc.net/problem/2873
(1000 이하) R 과 C가 주어지고, 각 행렬에 값이 주어집니다.
1,1 부터 시작해서 R,C 까지 이동하는데 적절히 선택하고 더해서,
최댓값을 만들어주는 길을 알려주면 됩니다.
이때, 상, 하, 좌, 우 4군데로 갈 수 있으며,
한 번 방문한 곳은 다시 방문할 수 없습니다.
(2) 풀이 도출
당연하지만 행이 홀수거나, 열이 홀수인 경우는 모든 곳을 방문할 수 있습니다.
행과 열이 모두 짝수인 경우가 사실 특별한데,
이 부분을 처리하는 방식을 찾는데 있어서 전략이 필요합니다.
그리고 손으로 몇가지 루트를 작성해보고,
거기서 얻은 핵심 힌트는 아래와 같습니다.
- 모든 곳을 방문할 수는 없다. 그럼 적당히 피해야하는건가?
- 그럼 피해야 하는 영역은, 최솟값과 관련이 있을 것 같다.
- 그리고 그 영역은 지나면 안된다. (이 최솟값인 장소는 행이나 열이 홀수인 순간)
- 최솟값인 영역 단 한군데만 피해 갈 수 있는 루트를 생성 할 수 있는가?
(3) Wrong Answer 코드 (dynamic programming)
dp[i][j][direction] : i, j 에 현재 direction 일 때 끝까지 도달한 경우의 최댓값
최초에 접근했던 잘못된 방식입니다.
direction 을 정하는 순간은 아래로 내려가는 상태에서만 가능했고,
그 외에는 정해진 방향대로 좌/우로가거나 아니면 내려가거나 3가지 경우,
즉 위로 가는 건 고려할 필요가 없다고 생각하고 아래와 같은 코드를 구현했었습니다.
이때 시간복잡도는,
$$ O(n^2) $$
입니다.
#include <cstdio>
#include <memory.h>
#include <algorithm>
using namespace std;
#define DOWN 0
#define LEFT 1
#define RIGHT 2
#define MINIMAL -(1e+8)
int e[1000][1000];
int dp[1000][1000][3]; // down, left, right
int nxt[1000][1000][3];
int r, c;
int dy(int cr, int cc, int direction) {
int &ret = dp[cr][cc][direction];
if (cr == r - 1) {
if (cc == c - 1) return 0;
else if (direction == LEFT) return MINIMAL;
else {
nxt[cr][cc][direction] = RIGHT;
return ret = e[cr][cc + 1] + dy(cr, cc + 1, RIGHT);
}
}
if (ret != -1)return ret;
ret = MINIMAL;
bool left_available = false;
bool right_available = false;
if (direction == DOWN) {
// can turn left, right
if (cc - 1 >= 0) left_available = true;
if (cc + 1 < c) right_available = true;
}
else {
if (direction == LEFT) {
if (cc - 1 >= 0)left_available = true;
}
else {
if (cc + 1 < c) right_available = true;
}
}
int tmp;
if (left_available) {
tmp = dy(cr, cc - 1, LEFT) + e[cr][cc - 1];
if (ret < tmp) {
nxt[cr][cc][direction] = LEFT;
ret = tmp;
}
}
if (right_available) {
tmp = dy(cr, cc + 1, RIGHT) + e[cr][cc + 1];
if (ret < tmp) {
nxt[cr][cc][direction] = RIGHT;
ret = tmp;
}
}
if (cr + 1 < r) {
tmp = dy(cr + 1, cc, 0) + e[cr + 1][cc];
if (ret < tmp) {
nxt[cr][cc][direction] = DOWN;
ret = tmp;
}
}
return ret;
}
int main() {
scanf("%d %d", &r, &c);
for (int i = 0; i < r; i++)for (int j = 0; j < c; j++) {
scanf("%d", &e[i][j]);
}
memset(dp, 0xff, sizeof(dp));
dy(0, 0, 0);
int cr = 0, cc = 0, cd = 0;
while (true) {
if (cr == r - 1 && cc == c - 1)break;
int ncd = nxt[cr][cc][cd];
if (ncd == DOWN) {
cr++, cd = DOWN;
printf("D");
}
else if (ncd == LEFT) {
cc--, cd = LEFT;
printf("L");
}
else {
cc++, cd = RIGHT;
printf("R");
}
}
puts("");
}
(4) 정답 코드
BOJ 2873 롤러코스터