[백준/BOJ] 1577 도로의 개수

문제 : 1577 도로의 개수

1577번: 도로의 개수

도시의 크기가 주어지고 공사 중인 도로의 크기가 주어졌을 때,

(0,0)에서 (N, M)까지 가는 경우의 수를 출력하는 문제이다.

도로가 정상적일 때 현재 위치기준 왼쪽+아래가 경우의 수 이므로

공사중인 도로인지 아닌지 체크하며 DP 배열을 채우면 된다.

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct ABC{
    ll a, b, c, d;
    ABC(){}
    ABC(ll a, ll b, ll c, ll d) : a(a), b(b), c(c), d(d) {}
};
bool operator<(ABC x, ABC y){
    if (x.a<y.a || (x.a==y.a && (x.b<y.b || (x.b==y.b && (x.c<y.c || (x.c==y.c && x.d<y.d))))))
        return 1;
    else
        return 0;
}
ll N, M, K, DP[105][105];
vector<ABC> arr;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M >> K;
    while (K--){
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        if (a>c || (a==c && b>d))
            arr.push_back({a,b,c,d});
        else
            arr.push_back({c,d,a,b});
    }
    DP[0][0]=1;
    sort(arr.begin(),arr.end());
    for (int i=0;i<=N;i++){
        for (int j=0;j<=M;j++){
            if (i-1>=0 && !binary_search(arr.begin(),arr.end(),ABC(i,j,i-1,j)))
                    DP[i][j]+=DP[i-1][j];
            if (j-1>=0 && !binary_search(arr.begin(),arr.end(),ABC(i,j,i,j-1)))
                    DP[i][j]+=DP[i][j-1];
        }
    }
    cout << DP[N][M];
    return 0;
}