(C++) - 백준(BOJ) 1937 : 욕심쟁이 판다

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

1937번: 욕심쟁이 판다

dp로 푼 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

상, 하, 좌, 우로 이동 및 비교를 위한 일차원 배열 dr, dc, 대나무 숲 정보를 저장할 이차원 배열 bamboo, 판다의 정보를 저장할 이차원 배열 live, 대나무 숲의 한 변 너비 n, 정답을 출력할 변수 ans를 선언해 줍니다.

📔 풀이과정

bfs혹은 dfs를 수행하려면 brute force처럼 i,j에 배치해 모든 경우의 수를 검사해 가장 긴 경로를 찾아야하는데

O(500*500*500)는 O(1억2천500만)으로 1초(1억번연산) 제한을 넘으므로 시간초과가 됩니다.

따라서 생각을 전환해야 합니다.

판다가 r행 c열에 배치된 후 상하좌우로 이동해 가며 1씩 경로가 더해지는 개념이 아닌 (r, c)에 배치될 경우 판다가 생존 가능한 기간으로 생각해봅니다.

판다는 (r, c)에 배치된 후 최대한 오래살기 위해, 대나무가 많아지는 방향으로 인접한 상,하,좌,우 칸중 하나를 선택해 이동하며 먹을 것입니다. 

 

재귀형식(top down dp)으로 구현하는 것이 위 생각과 맞아 떨어집니다.

이동할 수 있을 때까지 함수가 호출되고 끝에서 1을 반환해준다면 자신을 호출한 부모함수로 값을 전달하는 방식으로 동작하기 때문입니다. 

 

dp함수를 수행시 점화식은 다음과 같습니다.

r, c에서 생존가능기간 = max(r,c를 시작으로 유효한 어느 방식으로 이동했을 때 방문한 칸의 수 + 1)

 

모든 대나무의 좌표(행,열)들 중 dp함수를 수행한 결과값들 중 최대값를 ans에 저장해줍니다.

📔 정답출력

ans를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
using tiii = tuple<int,int,int>;

int dr[] = {0,0,1,-1}, dc[] = {1,-1,0,0};
int bamboo[501][501], live[501][501], n, ans;

int dp(int r, int c){
    int &ret = live[r][c];
    if(ret) return ret;
    ret = 1;
    for(int i = 0; i < 4; i++){
        int nr = r + dr[i];
        int nc = c + dc[i];
        if(0 > nr || nr >= n || 0 > nc || nc >= n) continue;
        if(bamboo[r][c] >= bamboo[nr][nc]) continue;
        ret = max(ret,dp(nr, nc) + 1);
    }
    return ret;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> bamboo[i][j];

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            ans = max(ans,dp(i,j));

    cout << ans;
}