아이템 획득( BOJ 28216 )

문제 : https://www.acmicpc.net/problem/28216

28216번: 아이템 획득

 

문제 파악하기

자동차가 Q번 이동하면서 획득한 상자의 아이템 개수를 구하는 문제입니다. 자동차는 (1, 1) 위치에서 시작하며, 이동하면서 만나는 상자에서 항상 아이템을 얻을 수 있습니다. 상자와 이동하는 횟수 모두 최대 200,000번이기에 전탐색으로는 문제를 해결할 수 없습니다. 하지만 x와 y의 값이 최대 200,000이라는 범위 안이기 때문에 x와 y축을 기준으로 적절하게 상자를 저장하면 빠르게 문제를 해결할 수 있습니다.

 

문제 해결하기

우선 val[idx][sw] 배열을 만들어 상자들의 위치를 관리할 수 있습니다. val[idx][sw] 배열에는 sw의 값에 따라 x축(sw=0) 혹은 y축(sw=1)을 기준으로 idx인 값들을 저장합니다. 예를 들어 val[7][0]은 x축 기준으로 x=7인 상자들의 y값을 저장합니다. 이렇게 저장할 수 있는 근거는 자동차의 움직임으로, 자동차는 항상 동서남북 중 한 방향으로만 움직입니다. 그렇기에 한 번의 움직임에 바뀌는 값은 x와 y값 중 1개이며, 우리는 변하는 값만 신경쓰면 되기 때문입니다. 예를 들어 d=0인 경우에는 x값이 증가하는 방향으로 움직입니다. 이 경우에 y값은 변화하지 않기에 val[y][1]에 저장된 상자들의 x값만 확인하면 되며, 나머지 불필요한 상자들은 확인하지 않기에 이전보다 효율적인 탐색이라고 할 수 있습니다.

 

하지만 이렇게 나누었다고 모든 경우를 빠르게 확인할 수는 없습니다. 만약 200,000개의 상자가 하나의 x값/y값을 가지고 있다면 어짜피 모든 상자를 살펴봐야 하기 때문입니다. 탐색을 좀 더 효율적으로 만드는 방법은 누적합을 활용하는 것입니다. 어짜피 자동차는 직선으로 움직이며 자동차의 현재 위치와 도착 위치 사이의 모든 상자들을 열어봅니다. 따라서 미리 아이템의 개수를 누적합으로 구해놓으면 현재 위치와 도착 위치 사이의 아이템 개수를 비교하여 구간 내 아이템의 개수를 구할 수 있습니다. 현재 위치와 도착 위치는 이분 탐색을 활용할 수 있으며, 이 경우 O(logN)만에 탐색할 수 있기에 정말 효율적인 알고리즘이라고 할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#import <stdio.h>
#import <vector>
#import <utility>
#import <algorithm>
#define NMAX 200010
#define lint long long int
#define PAIR pair<int, lint>
using namespace std;
 
int N, Q;
int x, y, w, d, v;
 
lint ans;
PAIR pos;
vector< PAIR > val[NMAX][2];
int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};
 
lint bSearch(int idx, int sw, int s) {
    int l, r, mid;
 
    l = 0;
    r = val[idx][sw].size()-1;
    while(l<=r) {
        mid = (l+r)/2;
 
        if(val[idx][sw][mid].first <= s) l = mid+1;
        else r = mid-1;
    }
 
    if(r < 0) return 0;
    else return val[idx][sw][r].second;
}
 
int main() {
    // 입력(아이템)
    scanf("%d %d", &N, &Q);
    for(int i=1;i<=N;i++) {
        scanf("%d %d %d", &x, &y, &w);
 
        // val[idx][0]: x값 기준으로 저장하기(x가 idx인 y값 저장하기)
        // val[idx][1]: y값 기준으로 저장하기(y가 idx인 x값 저장하기)
        val[x][0].push_back({y, w});
        val[y][1].push_back({x, w});
    }
 
    // 정렬 및 누적합
    for(int i=1;i<NMAX;i++) {
        for(int j=0;j<2;j++) {
            sort(val[i][j].begin(), val[i][j].end());
            for(int jj=1;jj<val[i][j].size();jj++) val[i][j][jj].second += val[i][j][jj-1].second;
        }
    }
 
    // 입력(이동)
    pos = make_pair(1, 1);
    for(int i=1;i<=Q;i++) {
        scanf("%d %d", &d, &v);
 
        // 이동하면서 얻게 된 아이템 처리
        if(d == 0) ans += ( bSearch(pos.second, 1, pos.first+v) - bSearch(pos.second, 1, pos.first) );
        else if(d == 1) ans += ( bSearch(pos.first, 0, pos.second+v) - bSearch(pos.first, 0, pos.second) );
        else if(d == 2) ans += ( bSearch(pos.second, 1, pos.first-1) - bSearch(pos.second, 1, pos.first-v-1) );
        else ans += ( bSearch(pos.first, 0, pos.second-1) - bSearch(pos.first, 0, pos.second-v-1) );
 
        // 현재 위치 처리
        pos = make_pair(pos.first+dx[d]*v, pos.second+dy[d]*v);
    }
 
    // 출력
    printf("%lld", ans);
}

후기

누적합과 이분 탐색을 활용하는 문제였습니다. 정올 문제치고 추상화가 많이 필요하지 않았지만 이분 탐색을 활용하여 구현하는 방법을 연습할 수 있기에 정올을 준비하는 사람들에게 추천하고 싶은 문제입니다.