[BaekJoon][2411] 아이템 먹기

BAEKJOON ONLINE JUDGE

2411 아이템 먹기

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

DP

이동은 오른쪽, 위쪽만 가능하다 

 -> scv 문제와 비슷

아이템을 모두 먹어야 한다 

 -> 아이템을 먹으러 들려야 한다. 아이템 있는 곳으로 갈 때는 한 아이템에서 다른 아이템이 있는 위치로 이동하는 부분 경로, 부분 이동 경우의 수로 생각. 최종적으로는 각 아이템을 먹으러 이동하는 부분 경로를 곱하면 된다.

장애물이 있는 곳은 못가는 곳이므로 경로값 0

오른쪽, 위쪽만 가능하므로 시작 지점의 왼쪽과 아래는 갈 수 없는 부분. 경로값 0

시작은 (1, 1), 마지막은 (n, m)

그리고 C++에서 vector<pair<int, int> >를 쓸 때, >>에서 꼭 사이를 띄어주어야 컴파일 에러가 나지 않는다. 매번 실수하는 부분!

C++

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, m, itemCnt, blockCnt;
vector<pair<int, int> > item;
int map[101][101], dp[101][101];
 
int go(int starty, int startx, int endy, int endx)
{
    if (map[endy][endx])                                return 0;
    if (endy < starty || endx < startx)                return 0;
    if (endy == starty && endx == startx)    return 1;
    if (dp[endy][endx] != -1)                            return dp[endy][endx];
 
    return dp[endy][endx] = go(starty, startx, endy - 1, endx) + go(starty, startx, endy, endx - 1);
}
 
int main()
{
    int i, x, y;
    int ans;
 
    scanf("%d %d %d %d", &n, &m, &itemCnt, &blockCnt);
 
    for (i = 0; i < itemCnt; i++) {
        scanf("%d %d", &y, &x);
        item.push_back(make_pair(y, x));
    }
    for (i = 0; i < blockCnt; i++) {
        scanf("%d %d", &y, &x);
        map[y][x] = 1;
    }
 
    sort(item.begin(), item.end());
 
    memset(dp, -1, sizeof(dp));
 
    ans = go(1, 1, item[0].first, item[0].second);
    for (i = 1; i < item.size(); i++) {
        dp[item[i - 1].first][item[i - 1].second] = -1;
        ans *= go(item[i - 1].first, item[i - 1].second, item[i].first, item[i].second);
    }
    ans *= go(item[i - 1].first, item[i - 1].second, n, m);
 
    printf("%d\n", ans);
 
    return 0;
}

C

#include <stdio.h>
#include <string.h>
typedef struct tagPoint {
    int x, y;
}Point;
int n, m, itemCnt, blockCnt;
Point item[1001];
int map[101][101], dp[101][101];
void quicksort(int start, int end)
{
    int left = start, right = end;
    Point middle = item[(start + end) / 2];
    Point temp;
    while(left <= right)    {
        while (item[left].y < middle.y || 
                (item[left].y == middle.y && item[left].x < middle.x))     left++;
        while (item[right].y > middle.y || 
                (item[right].y == middle.y && item[right].x > middle.x))   right--;
        if (left <= right) {
            temp = item[left];
            item[left] = item[right];
            item[right] = temp;
            
            left++;
            right--;
        }
    }
    if (left < end)        quicksort(left, end);
    if (right > start)    quicksort(start, right);
}
int go(int starty, int startx, int endy, int endx)
{
    if (map[endy][endx])                    return 0;
    if (endy < starty || endx < startx)        return 0;
    if (endy == starty && endx == startx)    return 1;
    if (dp[endy][endx] != -1)                eturn dp[endy][endx];
    return dp[endy][endx] = go(starty, startx, endy - 1, endx) + go(starty, startx, endy, endx - 1);
}
int main()
{
    int i, x, y;
    int ans;
    scanf("%d %d %d %d", &n, &m, &itemCnt, &blockCnt);
    for (i = 0; i < itemCnt; i++) {
        scanf("%d %d", &y, &x);
        item[i].y = y;
        item[i].x = x;
    }
    for (i = 0; i < blockCnt; i++) {
        scanf("%d %d", &y, &x);
        map[y][x] = 1;
    }
    quicksort(0, itemCnt - 1);
    memset(dp, -1, sizeof(dp));
    ans = go(1, 1, item[0].y, item[0].x);
    for (i = 1; i < itemCnt; i++) {
        dp[item[i - 1].y][item[i - 1].x] = -1;
        ans *= go(item[i - 1].y, item[i - 1].x, item[i].y, item[i].x);
    }
    ans *= go(item[i - 1].y, item[i - 1].x, n, m);
    printf("%d\n", ans);
    return 0;
}