BOJ 2411 아이템 먹기

사용한 알고리즘

알고리즘 설명

맵을 위쪽 또는 오른쪽으로만 이동 가능하다.
이 이야기는, 각 y축에서 x축 기준으로 별이 처음 등장하는 좌표부터, 별이 마지막으로 등장하는 좌표까지는 플레이어가 반드시 지나가야 한다는 이야기이다.
이를 DP에 강제해 주게 되면, 한줄씩 DP에 표현하며 나타낼 수 있다.
DP(1, 1) = 1
DP(y, x) = DP(y-1, x) + DP(y, x-1). 단, 별이 처음 등장하는 y좌표 < x좌표 && 별이 마지막으로 등장하는 y-1좌표 < x좌표 를 만족해야한다.

풀이

// baekjoon 2411 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX_N 102

int N, M, A, B, x, y;
int matrix[MAX_N][MAX_N];
int StartPos[MAX_N], EndPos[MAX_N];
int dp[MAX_N][MAX_N];

int main() {
    scanf("%d %d %d %d", &N, &M, &A, &B);
    for (int i=0; i<A; i++) {
        scanf("%d %d", &x, &y);
        matrix[x][y] = 1;
    }

    for (int i=0; i<B; i++) {
        scanf("%d %d", &x, &y);
        matrix[x][y] = 2;
    }

    for (int i=1; i<=N; i++) {
        int minV=M+1, maxV=0;
        for (int j=1; j<=M; j++) {
            if (matrix[i][j] == 1) {
                minV = min(minV, j);
                maxV = max(maxV, j);
            }
        }
        StartPos[i]=minV;
        EndPos[i]=maxV;
    }

    dp[1][1]=1;
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=M; j++) {
            if (matrix[i][j] == 2) continue;
            if (j <= StartPos[i] && j >= EndPos[i-1]) dp[i][j] += dp[i-1][j];
            dp[i][j] += dp[i][j-1];
        }
    }
    printf("%d\n", dp[N][M]);
    return 0;
}