[C/C++] 백준 #1937 욕심쟁이 판다(동적 계획법)

격자로 나누어진 공간에서 판다가 대나무를 먹는데, 옮긴곳이 이전보다 대나무가 더 많은 곳이어야 옮겨갈 수 있습니다.

판다는 이동을 할 때, 상하좌우중 하나를 선택해서 한칸만 옮겨갈 수 있습니다.

이 판다가 최대한 많은 대나무숲에서 식사를 할 수 있도록 하고자 할 때, 최대 이동횟수를 구하는 문제입니다.

 

panda

 

조금 어려워보이지만, 

전 일단 탐욕 방법을 사용했습니다.  판다가 처음 위치한 곳의 대나무숲이 적은 곳이어야 한다는 것이죠.  그래서 최대로 많은 곳까지 가는 대나무숲을 고르는 것이죠.

 

\(V(s)\)의 값이 현재까지 이동한 횟수를 저장한다고 한다면, 

\[ V(s) = max_{s \rightarrow s'}(V(s'))+1

형태로 작성할 수 있습니다.

 

이것을 동적 계획법으로 풀기 위해서는 가장 적은 값부터 출발을 해주어야 합니다.  안 그러면, 중간이 출발점이 될 수 있기 때문이죠.

최소 지점부터 시작한다면, 다음에는 다익스트라 알고리즘을 쓰든 DFS 알고리즘을 쓰든 크게 상관은 없겠죠.  제 경우에는 효율을 위해서 동적 계획법을 썼습니다.  알고리즘 효율은 \(O(n^2 \log n)\) 으로 정렬 비용입니다.

 

//-----------------------------------------------------
//    baekjoon #1937
//        - by Aubrey Choi
//        - created at 2019-10-16
//-----------------------------------------------------
#include <stdio.h>
#include <algorithm>

static int dp[502*502], m[502*502];
bool cmp(int a, int b) { return m[a]<m[b]; }
int main()
{
    int n, v[500*500], ans=1;
    scanf("%d", &n);
    for(int i=0;i<n*n;i++) v[i]=(i/n+1)*(n+2)+(i%n+1), scanf("%d",&m[v[i]]);
    std::sort(v,v+n*n,cmp);
    int d[4]={n+2,1,-1,-n-2};
    for(int i=0;i<n*n;i++)
    {
        int s = v[i], max = 0;
        for(int j=0;j<4;j++) if(max<dp[s+d[j]]&&m[s+d[j]]!=m[s]) max=dp[s+d[j]];
        dp[s]=max+1; if(ans<max+1) ans=max+1;
    }
    printf("%d\n", ans);
}