백준 2169 로봇조종하기

처음에 아무생각없이 완전탐색으로 구했다가 시간초과를 맞았다.

 

시간제한은 1초인데 완전탐색으로 구하게되면 3*1000*1000이므로 초과가 된다.

그래서 메모리제이션기법을 사용해서 구했다.

 

#include <iostream>


//1000,1000, 세방향
//방향에따라 더해진것이 다르다.
int dist[1001][1001][3];
bool check[1001][1001];
int map[1001][1001];
using namespace std;
int N, M;
int dx[3] = { 0,-1,1 };
int dy[3] = { 1,0,0 };

int dp(int x, int y, int dir)
{
    if (y == N - 1 && x == M - 1)
        return map[N - 1][M - 1];
	//방향의 값을 레퍼런스로 가져오기
    int& ref = dist[y][x][dir];
    //만약 방향에 대한 값이 구해졌다면 리턴
    if (ref != -1000000)
        return ref;

    for (int i = 0; i < 3; ++i)
    {
        int nextx = dx[i] + x;
        int nexty = dy[i] + y;
		
        //만약 이쪽방향을 한번이라도 갔다면 트루
        if (check[nexty][nextx])
            continue;
        if (nextx < 0 || nexty < 0 || nextx >= M || nexty >= N)
            continue;
		//이쪽방향을 갈것이므로 트루로 설정
        check[nexty][nextx] = true;
        //dp돌리기
        ref=max(ref, dp(nextx, nexty, i)+ map[y][x]);
        //돌리고왔으니 뒤로 false
        check[nexty][nextx] = false;
    }
    return ref;
}
int main()
{
    cin >> N >> M;
    //y
    for (int i = 0; i < N; ++i)
    {  //x
        for (int j = 0; j < M; ++j)
        {
            cin >> map[i][j];
            for(int k=0; k<3; ++k)
            dist[i][j][k] = -1000000;
        }
    }
    check[0][0] = true;
    int bbb=dp(0, 0, 1);
    cout << bbb;

}