[BOJ] 2411 아이템 먹기

문제보기

처음에 x,y를 y,x로 바꿔보겠다고 하다가 좌표가 엉켜서 여러번 틀렸었다.

좌표가 위아래가 바뀌어있어서 상하반전으로 생각하고 풀었다.

그 후 벡터에 첫좌표, 끝좌표, 아이템들의 좌표를 넣고 정렬해준 후 ,

각 좌표 사이에 갈 수 있는 경로의 수를 DP로 구해서 전부 곱해주면된다.

---

#include <utility>

#include <vector>

#include <algorithm>

using namespace std;

int map[101][101] = {};

int getLoadNum(pair<int, int> n, pair<int, int> m){

int dp[101][101];

int x1 = n.first;

int y1 = n.second;

int x2 = m.first;

int y2 = m.second;

//printf("position:%d %d %d %d\n",y1,x1,y2,x2);

for(int i = x1;i<=x2;i++){

if(map[i][y1] == -1)break;

dp[i][y1] = 1;

}

for(int i = y1;i<=y2;i++){

if(map[x1][i] == -1)break;

dp[x1][i] = 1;

}

for(int i = x1+1;i<=x2;i++){

for(int j = y1+1;j<=y2;j++){

    if(map[i][j] != -1)

dp[i][j] = dp[i][j-1] + dp[i-1][j];

}

}

return dp[x2][y2];

}

int main(){

int N,M,A,B;

vector<pair<int, int> > aSpot;

scanf("%d%d%d%d",&N,&M,&A,&B);

int x,y;

for(int i = 0;i<A;i++){

scanf("%d%d",&x,&y);

aSpot.push_back(make_pair(x-1,y-1));

}

aSpot.push_back(make_pair(0,0));

aSpot.push_back(make_pair(N-1,M-1));

sort(aSpot.begin(),aSpot.end());

for(int i = 0;i<B;i++){

scanf("%d%d",&x,&y);

map[x-1][y-1] = -1;

}

int answer = 1;

for(int i = 0;i<aSpot.size()-1;i++){

int tp = getLoadNum(aSpot[i],aSpot[i+1]);

//printf("dd%d\n",tp);

answer *= tp;

}

printf("%d\n",answer);

}