BOJ 1937번 욕심쟁이 판다

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

github : https://github.com/junho0956/Algorithm/blob/master/1937/1937/%EC%86%8C%EC%8A%A4.cpp

 

dfs 와 dp 를 이용하여 문제를 해결하였습니다.

dp[n][m] : (n,m) 에서 이동할 수 있는 최대 횟수를 저장하는 의미

 

lis 알고리즘과 관련된 문제인데 아마도 dfs 와 dp로 돌리는거와 마찬가지로

각 좌표마다 가장 길게 만들 수 있는 부분수열을 찾으라는 의미일 것이다(?) 결국 dfs 돌리시면 됩니다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
 
typedef pair<int, int> pii;
int n;
int arr[501][501];
bool visit[501][501];
int dp[501][501];
int my[4] = { -1,1,0,0 };
int mx[4] = { 0,0,1,-1 };
 
int solve(int y, int x, int pre) {
 
    if (arr[y][x] <= pre) return 0;
 
    int& res = dp[y][x];
    if (res != -1) return res;
 
    visit[y][x] = true;
    int ans = 0;
    for (int i = 0; i < 4; i++) {
        int yy = y + my[i];
        int xx = x + mx[i];
        if (yy >= 0 && yy < n && xx >= 0 && xx < n && !visit[yy][xx]) {
            ans = max(ans, solve(yy, xx, arr[y][x]) + 1);
        }
    }
 
    visit[y][x] = false;
    return res = ans;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> arr[i][j];
 
    memset(dp, -1, sizeof(dp));
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans = max(ans, solve(i, j, 0));
        }
    }
 
    cout << ans;
    return 0;
}

 

복습 20.02.10