이동하기 [백준 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)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.
문제 풀이
풀이 과정
- 입력받는 미로의 크기와 같은 크기의 DP 배열을 생성한다.
- 미로 배열의 가로 0번째 값을 조건에 맞게 DP 배열에 입력한다.
- 미로 배열의 세로 0번째 값을 조건에 맞게 DP 배열에 입력한다.
- 미로배열 [ 1 ] [ 1 ] 값 부터 전에 있던 값들과 비교하여 더 큰 값이 내용으로 입력되도록 한다.
- DP 배열의 제일 마지막값 DP[height - 1] [width - 1] 값을 출력한다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
int width = 0, height = 0;
cin >> height >> width;
vector< vector <int> > board(height, vector<int> (width, 0));
vector< vector <int> > dp(height, vector<int> (width, 0));
// 미로 값 입력
for(int i = 0; i < height; i++) {
for(int j = 0; j < width; j++) {
int value = 0;
cin >> value;
board[i][j] = value;
}
}
// 시작점 초기화
dp[0][0] = board[0][0];
// 가로 0 번째 줄 초기화
for(int i = 1; i < width ; i++) {
dp[0][i] = board[0][i] + dp[0][i - 1];
}
// 세로 0 번째 줄 초기화
for(int i = 1; i < height; i++) {
dp[i][0] = board[i][0] + dp[i - 1][0];
}
// 동적 프로그래밍 시작
for(int i = 1; i < height; i++) {
for(int j = 1; j < width; j++) {
int temp_first = board[i][j] + dp[i][j - 1];
int temp_second = board[i][j] + dp[i - 1][j];
dp[i][j] = max(temp_first, temp_second);
}
}
cout << dp[height - 1][width - 1];
return 0;
}
문제 푼 소감
전형적인 DP문제의 예제였던 것 같다. 배열의 크기를 비교하는 과정을 신경써서 한다면 쉽게 풀 수 있을 것 같다.