Cereal( BOJ 18878 )

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

18878번: Cereal

 

문제 파악하기

소들이 자신의 선호도 순위대로 시리얼을 먹거나 시리얼을 포기할 때, 0마리 ~ (i-1)마리 소가 앞에서부터 하나씩 사라지는 동안 시리얼을 먹을 수 있는 소의 마릿수를 구하는 문제입니다. 소들은 다음 3단계에 걸쳐서 시리얼을 먹거나 포기한다고 합니다.

(1) 가장 좋아하는 시리얼이 남은 경우, 해당 시리얼을 먹습니다.

(2) 만약 가장 좋아하는 시리얼을 누군가 먼저 먹었다면, 그 다음으로 좋아하는 시리얼을 먹습니다.

(3) 그 다음으로 좋아하는 시리얼까지 누군가 먼저 먹었다면, 그 소는 시리얼을 포기하고 먹지 않습니다.

 

0마리부터 (i-1)마리 소가 앞에서부터 하나씩 사라질 때, 시리얼을 먹을 수 있는 소의 최대 마릿수를 구해야 합니다. 다만, 소의 마릿수가 최대 100,000마리이기 때문에 단순히 앞에서부터 한 마리씩 없애는 중첩 반복문을 사용해서는 문제를 해결할 수 없습니다. 하지만 생각의 관점을 반대로 바꾸면 문제를 풀 수 있습니다.

 

문제 해결하기

이 문제를 풀기 위해서는 뒤에서부터 소가 시리얼을 먹는다고 생각해야 합니다. 뒤에서부터 소가 시리얼을 먹으면서 현재 먹을 수 있는 시리얼의 최댓값을 뒤에서부터 하나씩 구해주면 됩니다. 그럼 왜 앞에서 소를 없애면서 마릿수를 구하면 시간초과가 나지만 뒤에서부터 마릿수를 구하면 훨씬 빠르게 구할 수 있을까요?

 

이는 항상 앞의 소가 시리얼을 먼저 가져간다는 특징 때문입니다. 앞에 소가 시리얼을 먼저 가져가기에 우리는 다음 소가 두 번째로 좋아하는 시리얼을 가져갈 수 있는지 확인하면 됩니다. 만약 두 번째로 좋아하는 시리얼을 아무도 가져가지 않았다면 탐색을 종료하면 됩니다. 하지만 누군가 시리얼을 가지고 있다면 이제는 해당 소의 순서를 자신의 순서와 비교해서 만약 자신보다 앞이라면 시리얼을 포기하고, 자신이 앞이라면 시리얼을 빼앗으면 됩니다. 그리고 빼앗긴 소는 다시 다음 시리얼을 먹을 수 있는지 확인하면 됩니다. 이렇게 빼앗긴 소가 다음 위치를 탐색하는데 소요되는 시간은 앞에서부터 맨 뒤에 있는 모든 소를 탐색하는 시간보다 확실히 짧게 걸린다는 건 쉽게 짐작할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <vector>
#include <utility>
#define NMAX 100010
#define PAIR pair<int, int>
using namespace std;
 
struct INP {
    int s, idx;
};
 
int N, M, f, s;
PAIR inp[NMAX];
 
int nxtS, nxtIdx;
 
int cnt;
int ans[NMAX];
INP visited[NMAX];
 
void sv(int cur, int idx) {
    if(cur < 0) return;
 
    // 만약 새로운 시리얼을 찾았다면
    if(!visited[cur].idx) {
        cnt++;
        visited[cur] = {-1, idx};
    }
    else {
        // 두번째 시리얼도 먼저 가져간 사람이 있다면
        if(visited[cur].idx < idx) return;
        else {
            int nS = visited[cur].s;
            int nI = visited[cur].idx;
            visited[cur] = {-1, idx};
 
            // 시리얼을 뺏긴 소의 다음 시리얼 탐색
            sv(nS, nI);
        }
    }
}
 
int main() {
    // input
    scanf("%d %d", &N, &M);
    for(int i=1;i<=N;i++) scanf("%d %d", &inp[i].first, &inp[i].second);
 
    // 뒤에서부터 넣기
    for(int i=N;i>=1;i--) {
        f = inp[i].first;
        s = inp[i].second;
 
        // 아무도 가져가지 않았다면
        if(!visited[f].idx) {
            visited[f] = {s, i};
            cnt++;
        }
        else {
            // i번째 소가 이전에 가져간 소보다 항상 먼저 가져감
            nxtS = visited[f].s;
            nxtIdx = visited[f].idx;
            visited[f] = {s, i};
 
            // 시리얼을 뺏긴 소가 가져갈 수 있는 시리얼 찾기
            sv(nxtS, nxtIdx);
        }
 
        ans[i] = cnt;
    }
 
    for(int i=1;i<=N;i++) printf("%d\n", ans[i]);
 
}

후기

역시 USACO 문제답게 간단하지 않고 흥미로운 문제였습니다. 뒤에서부터 쿼리를 시작하기에 오프라인 쿼리라고 생각할 수도 있고, 재귀적인 탐색을 사용했기에 재귀 문제라고도 할 수 있지만 개인적인 의견으로는 재귀 응용 문제로 소개하는게 좋지 않을까 생각합니다. 개인적으로 적당히 고민하고 적당히 구현하는 재미있는 문제였습니다.