BOJ 1520 - 내리막 길

문제 태그 : https://www.acmicpc.net/problem/1520

문제 설명

문제 풀이 (사고의 흐름)

(1,1)에서 (n,m)으로 갈 수 있는 경우의 수 찾기. 경우의 수를 찾는 것이고, 어떤 칸까지 갈 수 있는 경우의 수는 그 칸으로 올 수 있는 경우의 수의 합으로 표현된다. 따라서 이 문제는 2차원 DP로 해결 할 수 있다.
2차원 필드에서 진행되는 보통의 간단한 DP 문제 같은 경우에는 오른쪽 혹은 아래로 밖에 움직이지 못한다. 따라서 (i,j)는 (i-1,j)와 (i,j-1)로 표현이 된다. 하지만 이 문제는 그렇지 않다. 어떤 (i,j)의 칸으로 올 수 있는 칸은 주위의 4칸 중 (i,j)보다 숫자가 큰 칸이다. 따라서 (i,j)에 대한 경우의 수를 확실하게 구하기 위해서는 주변에 있는 칸들 중 칸의 값이 더 큰 칸에 대한 경우의 수를 모두 알고 있어야 한다. 
이를 해결하기 위해서 DP 테이블을 배열 값이 가장 큰 값부터 채워나가면 된다. 그러면 어떤 칸의 값을 구하기 위한 정보를 얻을 수 있다. 잊으면 안된다. DP식이 성립하기 위해서는 어떤 칸의 식에 들어갈 요소들이 확실히 알고있는 값이어야한다.
아무튼 DP테이블의 크기는 O(N^2) 한 칸당 걸리는 시간복잡도는 상수이므로 총 시간복잡도 O(N^2)에 문제를 해결할 수 있다.

코드 

 

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
struct poi{
    ll row,col,val;
};
bool sf(poi a,poi b)
{
    return a.val>b.val;
}
poi dat[505050];
ll arr[505][505];
ll dp[505][505];
 
int main()
{
    ll i,j,k,l,m,n,a,b,c,cnt=0;
    scanf("%lld %lld",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            scanf("%lld",&k);
            arr[i][j]=k;
            cnt++;
            dat[cnt].val=k;
            dat[cnt].row=i;
            dat[cnt].col=j;
        }
    sort(dat+1,dat+1+cnt,sf);
    for(i=1;i<=cnt;i++)
    {
        ll r=dat[i].col;
        ll c=dat[i].row;
        if(r==1&&c==1)
        {
            dp[1][1]=1;
            continue;
        }
        if(arr[c][r]!=arr[c-1][r]) dp[c][r]+=dp[c-1][r];
        if(arr[c][r]!=arr[c+1][r]) dp[c][r]+=dp[c+1][r];
        if(arr[c][r]!=arr[c][r-1]) dp[c][r]+=dp[c][r-1];
        if(arr[c][r]!=arr[c][r+1]) dp[c][r]+=dp[c][r+1];
    }
    printf("%lld",dp[n][m]);    
}