[BOJ] 2411 - 아이템 먹기

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

BOJ - 아이템 먹기

문제 유형: 다이나믹 프로그래밍

문제 난이도: Gold IV

시간 제한: 2초

메모리 제한: 128MB

 

문제

N×M 모양의 맵에 아이템과 장애물이 있다. 이때 맵의 왼쪽 아래에서 출발하여 오른쪽 위로 가려고 하는데, 중간에 모든 아이템을 먹으려고 한다. 이동할 때에는 오른쪽이나 위쪽으로만 이동할 수 있다. 또, 장애물이 있는 곳으로는 지날 수 없다.

이때, 이동하는 경로의 개수가 총 몇 개인지 알아내는 프로그램을 작성하시오. 위의 예에서 ◎은 장애물, ☆는 아이템이다. 이때 경우의 수는 4 가지가 된다.

 

입력

첫째 줄에 N, M(1 ≤ N, M ≤ 100), A(1 ≤ A), B(0 ≤ B)가 주어진다. A는 아이템의 개수이고, B는 장애물의 개수이다. 다음 A개의 줄에는 아이템의 위치, B개의 줄에는 장애물의 위치가 주어진다. 위치를 나타낼 때에는 왼쪽 아래가 (1, 1)이 되고 오른쪽 위가 (N, M)이 된다.

 

출력

첫째 줄에 경우의 수를 출력한다. 이 값은 int 범위이다.

 

풀이

장애물은 mat에 표시히고, 각 아이템점을체크포인트로 만들어서 (0, 0), (n-1, m-1)까지 같이 넣어서 정렬한다.

그러고 각 체크포인트들을 순차적으로 이동하면 된다.

 

dp[i][j] = (i, j)까지 오는 경우의 수라고 하고, dp[0][0]은 1이 된다. 

 

그 뒤, (이전row, 이전col) -> (다음row, 다음col)의 부분 2D배열에서 경우의 수를 업데이트한다.

장애물은 dp가 0이 되겠고,

dp[i][j]는 dp[i-1][j] 또는 dp[i][j-1]로부터 올 수 있다. 즉, 둘의 합이다.

 

최종적인 dp[n][m]을 출력하면 된다.

 

코드

C++

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

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

    int n, m, a, b;
    cin >> n >> m >> a >> b;

    vector<vector<int>> mat(n, vector<int>(m, 0));
    vector<pii> checkpoints;

    for (int i = 0; i < a; i++) {
        int r, c;
        cin >> r >> c;
        checkpoints.emplace_back(r - 1, c - 1);
    }

    checkpoints.emplace_back(0, 0);
    checkpoints.emplace_back(n - 1, m - 1);
    sort(checkpoints.begin(), checkpoints.end());

    for (int i = 0; i < b; i++) {
        int r, c;
        cin >> r >> c;
        mat[r - 1][c - 1] = 1;
    }

    vector<vector<int>> dp(n, vector<int>(m, 0));
    if (mat[0][0] == 0) dp[0][0] = 1;

    for (int k = 1; k < checkpoints.size(); ++k) {
        int prevR = checkpoints[k - 1].first;
        int prevC = checkpoints[k - 1].second;
        int nextR = checkpoints[k].first;
        int nextC = checkpoints[k].second;

        for (int i = prevR; i <= nextR; ++i) {
            for (int j = prevC; j <= nextC; ++j) {
                if (mat[i][j] == 1) {
                    dp[i][j] = 0;
                    continue;
                }
                if (i == prevR && j == prevC) continue;
                dp[i][j] = 0;
                if (i > prevR) dp[i][j] += dp[i - 1][j];
                if (j > prevC) dp[i][j] += dp[i][j - 1];
            }
        }
    }

    cout << dp[n - 1][m - 1] << "\n";
    return 0;
}