[백준/C++] 11048번: 이동하기
- 문제
https://www.acmicpc.net/problem/11048
11048번: 이동하기
준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는
www.acmicpc.net
다이나믹 프로그래밍 알고리즘 문제이다.
- 코드
#include <iostream>
using namespace std;
int N = 0;
int M = 0;
int str[1000][1000] = { 0, };
int main(){
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> str[i][j];
}
}
int sum[3] = { 0, };
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (i == 0 && j == 0) {
continue;
}
else if (i == 0) {
str[i][j] += str[i][j - 1];
}
else if (j == 0) {
str[i][j] += str[i - 1][j];
}
else {
sum[0] = str[i - 1][j];
sum[1] = str[i][j - 1];
sum[2] = str[i - 1][j - 1];
if (sum[0] >= sum[1]) {
if (sum[0] >= sum[2]) {
str[i][j] += sum[0];
}
else if (sum[2] > sum[0]) {
str[i][j] += sum[2];
}
}
else if (sum[1] > sum[0]) {
if (sum[1] >= sum[2]) {
str[i][j] += sum[1];
}
else if (sum[2] > sum[1]) {
str[i][j] += sum[2];
}
}
}
}
}
cout << str[N - 1][M - 1] << endl;
}
- 풀이
Bottom up 방식을 사용해서 반복문으로 탐색하여 str 배열에 더해갔다. str[0][0]은 더할게 없다. 행이 0번째일 경우 왼쪽 열만 고려하면 되므로 최대 사탕 개수는 왼쪽을 더해주면 된다. 열이 0일 때도 같은 방법이다. 그 외일 경우 현재 위치의 왼쪽, 위, 왼쪽 대각선의 누적 사탕수를 비교해서 가장 큰 수를 더해가면 된다. n-1 행의 m-1 열 번째 누적 사탕을 구해야하므로 반복문을 빠져나온 후 출력한다.