11048번

11048번 - 이동하기

처음에 완전탐색으로 풀었을 때, 시간 초과가 걸렸다.

사실 시간안에 풀 수 있다고 생각하고, 완전탐색으로 풀었는데 시간초과가 떠서 당황했다.

그리고 이 문제를 풀때, DP에 쓰이는 D값을 평상시 처럼 0으로 초기화했던 것이 문제였다.

사탕의 갯수가 0개 일 수 있기 때문에, D값에 0이 들어갈 수 있다는 점을 인지하고, -1로 초기화 했어야 했다.

<정답 코드>

#include<iostream>
#include<algorithm>
#include<string.h>
 
using namespace std;
int dx[3] = { 0,-1,-1 };
int dy[3] = { -1,-1,0 };
int map[1001][1001];
int D[1001][1001];
 
int N, M, ans = 0;
 
int go(int x, int y)
{
    if (x == 1 && y == 1)
    {
        return map[1][1];
    }
 
 
    if (D[x][y] >= 0)
    {
        return D[x][y];
    }
 
 
    for (int d = 0; d < 3; d++)
    {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if (nx >= 1 && ny >= 1 && nx <= N && ny <= M)
        {
            D[x][y] = max(D[x][y], go(nx, ny) + map[x][y]);
        }
    }
    
    
    return D[x][y];
 
}
int main()
{
    cin >> N >> M;
 
    memset(D, -1, sizeof(D));
 
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            cin >> map[i][j];
        }
    }
    
    cout << go(N,M) << endl;
 
    return 0;
}