[BOJ 11048 // C++] 이동하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 11048번 문제인 이동하기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11048

11048번: 이동하기

이 문제에서는 미로의 칸을 위에서 아래 행 방향으로, 같은 행이라면 왼쪽에서 오른쪽 열 방향으로 둘러보면서 이 칸으로 진입할 때 왼쪽에서 진입하는 것과 위쪽에서 진입하는 것중 어떤 경우에 더 많은 사탕을 얻는지 살펴 기록해나가는 것으로 풀 수 있다.

 

대각선 방향의 이동은 따로 고려할 필요가 없는데, 가장 많은 사탕을 줍는 경로 중 최단거리까지 구하는 것을 문제가 요구하고 있지 않기 때문이다.

대각선 방향의 이동이 포함된 경로가 가장 많은 사탕을 줍는 경로라면, 그 대각선 경로 대신 아래방향 한칸 이동과 오른쪽방향 한칸 이동을 대신 해도 기존 경로에 있는 사탕을 모두 주으므로 오른쪽방향 이동과 아래방향 이동만 고려해도 상관이 없다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <cmath>
using std::cin; using std::cout;
using std::max;
int arr[1001][1001];

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int row, column; cin >> row >> column;

    int x;

    for (int i = 1;i <= row;i++) {
        for (int j = 1;j <= column;j++) {
            cin >> x; arr[i][j] = x;
            arr[i][j] += max(arr[i-1][j], arr[i][j-1]);
        }
    }
    cout << arr[row][column];

    return 0;
}