[BOJ] 백준 21923. 곡예 비행 (Gold IV) 탑다운 DP

문제는 아래와 같다.

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

21923번: 곡예 비행

그림만 보고 1초 정도 투포인터가 생각난 문제.

재밌어 보이는 문제였는데, 생각보다 삽질을 좀 했다.

 

간단하게 해설 및 주의포인트들을 살펴보도록 하겠다.

---

의식의 흐름 및 해설

이 문제같은 경우는 상향으로 비행할 때와 하향으로 비행할 때, dp 점화식이 달라지기 때문에 dp 함수를 2개로 나누는 것이 훨씬 편하다. 처음에는 한꺼번에 처리하려 했으나, if문 남발이 너무 심해져서 따로 분리해서 해결하였다.

 

주의할 점은 아래와 같다.

1. dp 값이 -1이 가능하다. 따라서 dp테이블 초기화를 -1로 할 경우 오답이 나올 수 있다.
2. y, x 범위에 주의하자. 범위 바깥으로 비행하지 않도록 주의하자. 범위에 따라 dp 점화식이 조금씩 달라진다.
3. 격자가 1e3*1e3개이고, 최대 1e5의 값을 가질 수 있으므로 long long을 사용하자.

또한, 하향 비행은 도착점이 매번 고정돼있어 상관없으나,

상향비행은 도착점이 매번 변경되므로, 문제를 풀기 편하게 출발점을 도착점으로, 도착점을 출발점으로 잡아서 진행하였다. 즉, 상향비행을 하향비행처럼 놓고 풀은 것이다.

 

dp1: 상향비행 -> 하향비행인 척하는 상향비행

dp2: 하향비행

 

으로 접근하였으며,

dp1의 출발점은 (i, j), 도착점은 (N-1, 0)이며, 이동가능방향은 아래, 왼쪽이다.

dp2의 출발점은 (i, j), 도착점은 (N-1, M-1)이며, 이동가능방향은 아래, 오른쪽이다.

 

문제에서 출발점(상향비행에선 도착점)의 점수는 2번 더하므로, 위와 같이 나눠서 푸는 것이 의도한 풀이인 듯하다.

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAX = 1001;
const ll INF = 1e15;
ll N, M, a[MAX][MAX], d[MAX][MAX][2];
bool visit[MAX][MAX][2];
// upper
ll dp1(int y, int x) {
	if (y == N - 1 && !x)
		return a[y][x];
	ll& ret = d[y][x][0];
	if (visit[y][x][0])
		return ret;
	ret = -INF;
	visit[y][x][0] = true;
	if (y < N)
		ret = max(ret, dp1(y + 1, x) + a[y][x]);
	if (x)
		ret = max(ret, dp1(y, x - 1) + a[y][x]);
	return ret;
}
// lower
ll dp2(int y, int x) {
	if (y == N - 1 && x == M - 1)
		return a[y][x];
	ll& ret = d[y][x][1];
	if (visit[y][x][1])
		return ret;
	visit[y][x][1] = true;
	ret = -INF;
	if (y < N)
		ret = max(ret, dp2(y + 1, x) + a[y][x]);
	if (x < M)
		ret = max(ret, dp2(y, x + 1) + a[y][x]);
	return ret;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> a[i][j];
		}
	}
	ll ans = -INF;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			ans = max(ans, dp1(i, j) + dp2(i, j));
		}
	}
	cout << ans << "\n";
}

---

예전에 memset(d, -1, sizeof(d)); 를 dp값으로 -1이 가능한 문제에서 사용했다가 맞왜틀을 외친적이 있었는데,

이번엔 잘 적용한 듯하다.

역시 머리가 좋지 않다면 많은 경험으로 강제로 머리에 집어넣게 하는 것이 중요한듯.