[백준 S1] 이동하기 (11048번)

www.acmicpc.net/problem/11048

11048번: 이동하기

문제

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

입력

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

소스코드 및 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
    int N, M;
    cin >> N >> M;

    vector< vector<int> > miro(N+1, vector<int>(M+1));
    
    for(int i=0; i<=N; ++i)
        miro[i][0] = 0;
    for(int i=0; i<=M; ++i)
        miro[0][i] = 0;

    int input;
    for(int i=1; i<=N; ++i) {
        for(int j=1; j<=M; ++j) {
            cin >> input;
            miro[i][j] = input + (miro[i-1][j] > miro[i][j-1] ? miro[i-1][j] : miro[i][j-1]);
        }
    }

    cout << miro[N][M] << endl;
    return 0;
}

* 처음에는 "이게 왜 DP 문제지?" 하고 입력 다 받고 완전 탐색으로 풀이했는데 시간초과가 났다.

* 입력을 받으면서 바로 계산해버려야 시간초과를 피할 수 있다. 다른 DP문제는 입력 전에 모든 케이스를 다 계산해두는 반면, 이 문제는 입력을 받으면서 계산을 해버리는 조금 다른 방식의 DP인 거 같다.