[Baekjoon] 이동하기

👀 문제 설명

문제

준규는 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)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

 

예제 입력 1

3 4

1 2 3 4

0 0 0 5

9 8 7 6

 

예제 출력 1

31

 

예제 입력 2

3 3

1 0 0

0 1 0

0 0 1

 

예제 출력 2

3

 

예제 입력 3

4 3

1 2 3

6 5 4

7 8 9

12 11 10

 

예제 출력 3

47

✍🏻풀이

위치를 이동하는 dp문제이다.

다른 문제들처럼 큐를 사용해 다음 위치를 큐에 넣는 방식으로 문제를 풀었는데, 메모리 초과가 났다.

같은 위치를 큐에 여러번 넣고 있기 때문에 큐의 크기가 거의 지수함수를 따라가고, 메모리 초과가 나는 것이었다.

 

큐를 사용하지 않고 for문을 사용해 각 위치에서 다음 위치로 이동해주니, 메모리 초과가 나지 않고 잘 풀렸다.

 

코드

#include <stdio.h>
#include <iostream>
#include <queue>

#define MAX 1001

using namespace std;

int dp[MAX][MAX];
int a[MAX][MAX];
int N, M;
int dx[3] = { 1, 0, 1 };
int dy[3] = { 0, 1, 1 };

int main() {
    cin >> N >> M;
    
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> a[i][j];
        }
    }
    
    // Queue를 사용하면 메모리 초과가 발생한다.
    // 이유) 같은 위치를 큐에 여러번 넣고 있기 때문에, 큐의 크기가 거의 지수함수를 따라 커진다.
    dp[1][1] = a[1][1];
    for (int x = 1; x <= N; x++) {
        for (int y = 1; y <= M; y++) {
            if (x == N && y == M)
                break;
            
            for (int dist = 0; dist < 3; dist++) {
                int nextX = x + dx[dist];
                int nextY = y + dy[dist];
                
                if (nextX < 1 || nextX > N || nextY < 1 || nextY > M)
                    continue;
                
                dp[nextX][nextY] = max(dp[nextX][nextY], dp[x][y] + a[nextX][nextY]);
            }
        }
    }
    
    cout << dp[N][M] << "\n";
    
    return 0;
}