[BOJ]백준 1937번: 욕심쟁이 판다/DP

www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

이차원 배열을 이용하는 DP문제 욕심쟁ㅇㅣ 판다🐼

 

1. 문제 정의

이차원 배열에서 특정 칸에서 연결된 상하좌우의 칸이 인접하다고 할 때, 인접한 칸이 현재 칸보다 숫자가 큰 최대 연결 회수 구하기

 

2. Recursion & Subproblem

4
14 9 12 10
1 11 5 4
7 15 2 13
6 3 16 8

위의 예시에서, 5의 최대 연결 수는 5-11-15로 3번이다.

이 때, 2의 최대 연결 수는 2-(5-11-15)로 4번이고, 이는 (5의 최대 연결 수+1)로 구할 수 있다.

따라서 특정 칸의 최대 연결 수 = max(인접한 칸 중 현재보다 숫자가 높은 칸의 최대 연결 수 + 1)이다.

 

3. Memoization & recurrence relation

2차원 배열에 대해 각각의 최대 연결 수를 구해야하기 때문에 n*n array(이차원)를 사용한다

2번에서 구한 subproblem에서, 특정 칸의 answer를 구하기 위해서는 인접한 칸 중 현재보다 숫자가 높은 칸의 answer를 먼저 구해야 하기 때문에 subproblem은 좌표값이 낮은 칸-> 좌표값이 높은 칸으로 dependent하다.

 

4. Psudo code

1️⃣ answer를 구하는 재귀함수를 최소 좌표값 순으로 실행시킨다

2️⃣ 현재 칸의 최대 연결 수가 이미 정해져있다면 해당 answer를 반환한다

3️⃣ 현재 칸의 최대 연결 수는 1로 초기화한다

4️⃣ 상하좌우 인접한 칸 중 현재 칸보다 좌표값이 크면서, 최대인 dp 값을 찾는다

5️⃣ 현재 칸의 최대 연결 수 = 인접 칸의 최대 연결 수 + 1로 정한 뒤 반환한다

 

5. Code

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 987654321
typedef struct { int k, x, y; }point;
int n, ans, arr[501][501], dp[501][501], dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
vector<point> v;
bool safe(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; }
bool cmp(point a, point b) { return a.k < b.k; }
int func(int x, int y) {
	if (dp[y][x] != INF)return dp[y][x];
	dp[y][x] = 1;
	int max = 1;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i], ny = y + dy[i];
		if (!safe(nx, ny) || arr[ny][nx] <= arr[y][x])continue;
		int t = func(nx, ny) + 1;
		if (t > max)max = t;
	}
	return dp[y][x] = max;
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			scanf("%d", &arr[i][j]);
			v.push_back({ arr[i][j],j,i });
			dp[i][j] = INF;
		}
	sort(v.begin(), v.end(), cmp);
	for (auto x : v)
		if (dp[x.y][x.x] == INF) {
			int k = func(x.x, x.y);
			if (k > ans)ans = k;
		}
	printf("%d", ans);
	return 0;
}

 

Time Complexity: O(N^2)