BOJ 11048 이동하기

문제 링크 : https://www.acmicpc.net/problem/11048 

11048번: 이동하기

 

dp 문제에서 top-down 방식과 bottom-up 방식의 시간을 비교하려고 풀어보았다.

규모가 너무 작아서 의미 있는 비교는 할 수 없었지만 몇 가지 언급하고 지나간다.

 

 

우선 문제의 조건에서 대각선 이동 (r,c)->(r+1,c+1) 은 필요가 없다.

사탕의 최댓값을 구하는 마당에 갈 수 있는 방을 건너뛸 이유가 있을까?

바텀업 방식의 코드부터 보자. 

 

#include<bits/stdc++.h>

using namespace std;

int N,M,grid[1001][1001],dp[1001][1001];

int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            scanf("%d",&grid[i][j]);

    dp[1][1]=grid[1][1];
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            if(i<N) dp[i+1][j]=max(dp[i+1][j], dp[i][j]+grid[i+1][j]);
            if(j<M) dp[i][j+1]=max(dp[i][j+1], dp[i][j]+grid[i][j+1]);
        }
    }
    
    printf("%d\n", dp[N][M]);
}

 

바텀업 방식에서도 i , j 에서 dp[i][j] 를 결정할 것인지, 아니면 dp[i][j] 가 기여하는 방식으로 진행할 것인지 선택할 수 있다.

위의 코드는 후자에 해당된다.

 

다음은 탑다운 방식이다.

 

#include<bits/stdc++.h>

using namespace std;

int N,M,grid[1001][1001],dp[1001][1001];

int recur(int r,int c){
    if(r==N && c==M) return grid[N][M];
    int &ret=dp[r][c];
    if(ret!=-1) return ret;
    
    if(r<N) ret=max(ret, recur(r+1,c)+grid[r][c]);
    if(c<M) ret=max(ret, recur(r,c+1)+grid[r][c]);
    
    return ret;
}

int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) scanf("%d",&grid[i][j]);
    memset(dp, -1, sizeof dp); 
    printf("%d\n",recur(1,1));
}

 

사실 이 글을 작성하는 이유는 실수가 있었기 때문이다. 

위의 바텀업 방식에서는 필요없었지만  dp를 -1 과 같은 특별한 값으로 초기화해 두지 않으면 시간초과가 발생한다.

미로의 마지막 부분이 왕창 0 으로 채워진 경우 dp 값이 0 이면 갔던 지점인지 아닌지 알 수가 없다.

목적칸에 하다못해 1 이라도 있으면 문제가 되지 않겠지만...

 

dp 값의 초기화는 습관에 의존하지 말고 늘 한 번 더 생각해서 설정하자.