| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 1735 | 620 | 348 | 29.048% |
문제
A나라와 B나라가 국경선을 놓고 몇 년째 싸우고 있다. 분쟁 지역의 크기는 직사각형이고, R×C 개의 칸으로 나누어져 있다. 모든 칸에는 사과 나무 또는 바나나 나무가 심어져 있다.
방금, 기나긴 영토 분쟁을 끝내기 위해 중립국에서 협상가 김상근이 도착했다. 상근이는 불도저를 이용해 일부 칸에 있는 나무를 모두 제거하고, 그러한 칸을 국경선으로 이용하려고 한다. 불도저는 가장 왼쪽 윗칸에서 출발하며, 한 칸 아래, 오른쪽, 오른쪽 아래 대각선으로 이동할 수 있다. 불도저는 오른쪽 아랫칸에 도착할 때까지 이동한다.
A는 불도저가 지나간 길의 아래쪽을 가지게 되고, B는 위쪽을 가지게 된다. 따라서, 땅을 하나도 받지 못하는 경우가 생길 수도 있다.
김상근은 A에 사는 사람들은 사과를 좋아하고, B에 사는 사람들은 바나나를 좋아한다는 사실을 알고 있다. 따라서, 불도저가 지나간 길의 아래쪽에 있는 사과 나무의 개수와 위쪽에 있는 바나나 나무 개수의 합을 크게 만들려고 한다.
가능한 합 중 가장 큰 합을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 땅의 크기 R과 C가 주어진다. (2 ≤ R,C ≤ 1500)
다음 R개 줄에는 각 칸에 심어져있는 나무와 개수가 주어진다. 사과는 A, 바나나는 B이고, 각 칸에 심어져 있는 나무의 개수는 1보다 크거나 같고, 99보다 작거나 같다.
출력
가능한 합 중 가장 큰 것을 출력한다.
접근
prefix summary를 이용해 DP table을 갱신하는 문제이다.
나는 오른쪽 아래부터 거꾸로 올라오면서 값을 갱신해주었다.
사과는 가로의 누적합을, 바나나는 세로의 누적합을 미리 구해주어야 한다.
그렇게 되면, 테이블을 갱신하는 점화식은 (사과 가로를 A, 바나나 세로를 B로 놓는다.
table[i - 1][j] = max(table[i - 1][j], table[i][j] + A[i][j - 1])
table[i][j - 1] = max(table[i][j - 1], table[i][j] + B[i - 1][j])
table[i - 1][j - 1] = max(table[i - 1][j - 1], table[i][j] + A[i][j - 1] + B[i - 1][j])
의 식이 나온다. 이는 위 혹은 옆으로 갈 때마다, A와 B의 땅으로 고정되기 때문에 그렇다.
풀이
각 노드의 누적합을 구해주기 위해 Node란 구조체를 만들었다.
여기에는 ax, by로 각 누적합을 멤버변수로 주고, 입력단계에서 해결해주었다.
이후 점화식을 코드로 옮긴 뒤 dp[1][1]을 출력해주면 된다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
struct Node
{
char what;
int cnt, ax, by;
Node() { ax = by = 0; }
};
int R, C, dp[1501][1501];
Node arr[1501][1501];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
CIN2(R, C);
FUP(i, 1, R)
{
FUP(j, 1, C)
{
CIN2(arr[i][j].what, arr[i][j].cnt);
arr[i][j].ax = arr[i][j - 1].ax;
arr[i][j].by = arr[i - 1][j].by;
if (arr[i][j].what == 'A') arr[i][j].ax += arr[i][j].cnt;
else arr[i][j].by += arr[i][j].cnt;
}
}
FDOWN(i, R, 1)
{
FDOWN(j, C, 1)
{
dp[i - 1][j] = max(dp[i - 1][j], dp[i][j] + arr[i][j - 1].ax);
dp[i][j - 1] = max(dp[i][j - 1], dp[i][j] + arr[i - 1][j].by);
dp[i - 1][j - 1] = max(dp[i - 1][j - 1], dp[i][j] + arr[i][j - 1].ax + arr[i - 1][j].by);
}
}
COUT(dp[1][1]);
return 0;
}