[백준] 11048번 - 이동하기

백준 11048번 문제 보기

문제풀이

1890번 점프, 1520번 내리막길과 비슷한 2차원 배열에서의 DP문제다.
문제자체는 간단한듯!

DP점화식

Top-Down방식으로 dp배열을 채웠는데
dp [x-1][y], dp [x][y-1], dp [x-1][y-1] 셋 중 가장 큰 값에 (x, y) 위치의 사탕 값을 더해준 값이 dp [x][y]에 들어간다.

---

Code

#include <iostream>
using namespace std;

int N,M;
int board[1000][1000];
int dp[1000][1000];
int visited[1000][1000];
int find(int x, int y);

int main(){
    cin >> N >> M;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin >> board[i][j];
            dp[i][j] = board[i][j];
        }
    }
    int ans = find(N-1,M-1);
    cout << ans;
    return 0;
}

int find(int x, int y){
    if(visited[x][y] == 1) return dp[x][y];
    int tmp = 0;
    if(x-1 >= 0)    tmp = max(tmp,find(x-1,y));
    if(y-1 >= 0)    tmp = max(tmp,find(x,y-1));
    if(x-1 >= 0 && y-1>=0)  tmp = max(tmp,find(x-1,y-1));
    dp[x][y] += tmp;
    visited[x][y] = 1;
    return dp[x][y];
}

---

visited배열을 만든 이유!

2차원 배열의 DP문제에서, find함수 내에서 해당 위치에 이미 수행된 dp값이 있는지를 체크하기 위해
dp배열 자체로 체크할 수 있는 상황도 있지만
visitied배열을 꼭 따로 만들어 줘야 하는 경우도 있다.
예를 들어 이 문제에서 find() 함수를 위의 Code처럼 만들지 않고 아래와 같이 만드는 상황을 생각해보자

int find(int x, int y){
    if(dp[x][y] != 0) return dp[x][y]; <--여기
    int tmp = 0;
    if(x-1 >= 0)    tmp = max(tmp,find(x-1,y));
    if(y-1 >= 0)    tmp = max(tmp,find(x,y-1));
    if(x-1 >= 0 && y-1>=0)  tmp = max(tmp,find(x-1,y-1));
    dp[x][y] += board[x][y];
    dp[x][y] += tmp;
    return dp[x][y];
}

"여기"라고 표시한 부분처럼 dp배열 자체로 체크를 할 수 있지 않을까?라고 생각했다.
이렇게 코딩해도 문제의 예제 3개는 모두 돌아가지만, 제출하면 시간 초과가 뜬다.!
반례를 찾아보고 이해했다!

6 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 1 1
0 0 0 0 1 1

input이 위와 같을 경우, 두 경우 모두 같은 결괏값이 나오지만
find함수의 아랫부분 코드의 수행 횟수는 각각
visited배열을 만들어 준 경우 : 36번
visited배열을 안 만들어 준 경우 : 2812번으로 엄청난 차이가 난다.

왜냐하면 (0,0)~(3,3)까지의 구간의 dp배열 값이 모두 0이기 때문에 수행하지 않은 걸로 간주하고
계속해서 값을 구해서 0이라는 값을 넣고...
또 수행하지 않은 것으로 간주하고... 이렇게 계속 반복되기 때문이다.