백준 1937 - 욕심쟁이 판다(복습)

문제 링크입니다 https://www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

 

다이나믹 프로그래밍 문제였습니다. 

문제만 읽으면 간단히 BFS, DFS로 풀 수 있는 문제지만 해당 알고리즘을 사용한다면 시간초과가 됩니다.

따라서 동적계획법과 회귀를 사용하여 푸는 문제입니다.

문제 조건입니다.

1. 자신이 있는 곳에서 상,하,좌,우 한곳으로 이동한다.

2. 이동한 곳에는 전에 있던 곳보다 대나무가 많아야한다.

3. 1,2조건을 만족하면서 최대한 오래 살아야한다.

 

저는 check라는 이차원 배열을 만들어서 각각의 칸에 해당 좌표에서 살 수 있는 최대한의 시간을 저장했습니다.

 

2(1,0)	3	4	5	6	7	8	9	10
1(0,0)	18(0,1)	17	16	15	14	13	12	11

이렇게 대나무가 주어졌다면 최대한으로 살 수 있는 시간은 18입니다.

(0,0) -> (1,0) -> (1,1) -> (1,2) -........> (0,1)로 이동하면서 살 수 있습니다.

만약 (0,0)에서 (1,0)으로 이동한다면 17이라는 값이 나옵니다. 하지만 (0,0) 에서 이동하는 것이 이미 큼으로 계산할 필요는 없음을 알 수 있습니다.

따라서 check배열에 값이 이미 있다면 다음 탐색을 하지 않고 return을 하면 된다는 것을 알 수 있습니다.

 

자세한 것은 코드를 참고해 주세요

 

#define CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>
using namespace std;

int bamboo[501][501];
int check[501][501];
int arr[4] = { 1,0,-1,0 };
int arr2[4] = { 0,1,0,-1 };
int num,ans;

int dfs(int x, int y) {
	if (check[x][y] != 0) return check[x][y];
	check[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		int xx = x + arr[i];
		int yy = y + arr2[i];
		if (xx >= 1 && xx <= num && yy >= 1 && yy <= num) {
			if (bamboo[x][y] < bamboo[xx][yy]) {
				check[x][y] = max(check[x][y], dfs(xx,yy) + 1);
			}
		}
	}
	return check[x][y];
}

void solve() {
	for (int i = 1; i <= num; i++) {
		for (int j = 1; j <= num; j++) {
			ans = max(ans, dfs(i, j));
		}
	}
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> num;
	for (int i = 1; i <= num; i++) {
		for (int j = 1; j <= num; j++) {
			cin >> bamboo[i][j];
		}
	}
	solve();
	return 0;
}

 

질문 및 조언 댓글 남겨주세요