[DP] 11048번 이동하기

11048번 이동하기

 

https://www.acmicpc.net/problem/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)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

 

예제 입력

3 4
1 2 3 4
0 0 0 5
9 8 7 6

3 3
1 0 0
0 1 0
0 0 1

4 3
1 2 3
6 5 4
7 8 9
12 11 10

 

예제 출력

31

3

47

 

해결방법

Shortest Path 유형의 DP 문제이다

 

 

⭐️ 솔루션 ⭐️

먼저 시작점 (1,1) 에서 (n,m) 까지 반복문을 돌며 최대값을 저장한다

이 때, (i,j) 의 사탕 최대값은 (i-1, j) (i, j-1) (i-1, j-1) 중의 최대값 + a[i][j] 이다

 

 

1️⃣ Bottom-up 방식

• 2중 for문으로 한 행씩 d 배열에 최대값을 저장한다
• Index는 1,1 부터 시작하는데 0행과 0열은 전부 0이기 때문에 따로 초기값을 설정해주지 않아도 된다

 

2️⃣ Top-down 방식

• 재귀를 사용해서 구현한다
• row, col 이 둘 다 1이라면 return 1을 해준다
• 만약 범위를 벗어나면 (row와 col이 1보다 작다면) return 0을 해준다
• memoization을 위해 d 배열을 -1로 초기화한다 (만약 d가 0보다 크다면 return d[row][col])

 

 

 

소스코드

1️⃣ Bottom-up

#include <iostream>
#include <cstring>
#include <math.h>
#include <algorithm>
#define MAX 1001
using namespace std;

int n,m;
int map[MAX][MAX];
int d[MAX][MAX];

void dp(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            d[i][j] = max(d[i-1][j-1],max(d[i-1][j],d[i][j-1])) + map[i][j];
        }
    }
    
    cout << d[n][m] << "\n";
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> map[i][j];
        }
    }
    
    dp();
    
    return 0;
}

 

2️⃣ Top-down

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 1001
#define INF 987654321
using namespace std;

int n,m;
int a[MAX][MAX];
int d[MAX][MAX];

int top_down(int row,int col){
    // 답을 찾았다면
    if(row==1 && col==1) return a[1][1];
    // 범위를 벗어난다면
    if(row<1 || col<1) return 0;
    // Memo가 되어있다면
    if(d[row][col] >= 0) return d[row][col];

    d[row][col] = max(max(top_down(row-1, col),top_down(row, col-1)),top_down(row-1, col-1)) + a[row][col];

    return d[row][col];
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> a[i][j];
        }
    }
    
    memset(d, -1, sizeof(d));
    cout << top_down(n, m) << endl;
}