[백준/C++] 11048번: 이동하기

• 문제

https://www.acmicpc.net/problem/11048

11048번: 이동하기

다이나믹 프로그래밍 알고리즘 문제이다.

• 코드

#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 열 번째 누적 사탕을 구해야하므로 반복문을 빠져나온 후 출력한다.