[백준 30804번] 과일 탕후루

문제 링크

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

 

문제 요약

1부터 9로 이루어진 수열이 주어진다. 이때, 연속된 부분 수열 중에서 숫자가 최대 두 개의 숫자로만 이루어진 부분 수열의 최대 길이를 구하는 문제이다.

 

문제 풀이

이 문제를 푸는 가장 효율적인 방법은 슬라이딩 윈도우 기법을 이용하는 것이다. 하지만 문제에서 주어진 제약 조건들을 잘 활용하면 조금은 더 간단한 방법으로 문제를 해결할 수 있다. 이 문제가 Division 1, Division 2에 동시에 출제된 것을 보면 다양한 접근 방법을 생각할 수 있게 의도된 문제로 보인다.

 

문제의 제약 조건을 활용하면 더욱 효과적이고 빠른 해결 방법을 찾을 수 있기 때문에, 문제를 풀기 전에 제약 조건을 먼저 확인하는 것이 중요하다는 이유를 잘 설명해 주는 모법적인(?) 문제라고 생각한다.

 

조금은 거친 방법으로 문제를 풀기

이 문제에서 주어진 두 개의 제약조건을 생각해보자. 첫 번째는 수열을 이루고 있는 숫자는 1부터 9까지라는 것이다. 두 번째는 최대 두 개의 숫자로만 이루어진 연속된 부분 수열의 최대 길이를 구해야 한다는 것이다. 이 두 가지 조건을 이용하면 우리는 조금은 거친 방법을 생각해 볼 수 있다.

 

만약에 우리가 연속된 부분 수열을 이루고 있는 숫자 두 개를 미리 정하고, 그 조건을 만족하는 연속된 부분 수열의 최대 길이를 구하는 문제를 푼다고 생각해 보자. 주어진 수열에서 숫자 \(P_1\) 또는 \(P_2\)로 이루어진 연속된 부분 수열들 중 최대 길이를 구하는 코드는 아래와 같이 작성할 수 있다.

int func(int p1, int p2) {
    for (int i = 0 ; i < n ; ++i) {
        P[i] = (A[i] == p1 || A[i] == p2);
    }
    
    int ret = 0, cnt = 0;
    
    for (int i = 0 ; i < n ; ++i) {
        if (P[i]) {
            cnt += 1;
        } else {
            cnt = 0;
        }
        
        ret = max(ret, cnt);
    }
    
    return ret;
}

그렇다면 우리가 생각해봐야 하는 \(P_1\), \(P_2\)의 쌍의 개수는 수열을 이루고 있는 숫자가 최대 9개이므로 \({}_9 \mathrm{ C }_2\)이다. 함수 func의 시간 복잡도가 \(\mathcal{O}(N)\)이기 때문에 모든 경우에 대해 func 함수를 계산해도 주어진 제한시간 내에 충분히 들어올 수 있다.

int ans = 0;
    
for (int i = 1 ; i <= 9 ; ++i) {
    for (int j = i + 1 ; j <= 9 ; ++j) {
        ans = max(ans, func(i, j));
    }
}

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

 

슬라이딩 윈도우 기법으로 문제 풀기

다음으로 이 문제를 효율적인 방법으로 풀 수 있는 슬라이딩 윈도우 기법을 이용한 풀이를 알아보자. 어떠한 연속된 구간 [lo, hi]가 있을 때 이 구간을 이루고 있는 숫자의 개수가 두 개보다 많다면, hi를 증가시켜도 그 구간을 이루고 있는 숫자의 개수는 두 개보다 같거나 작아질 수 없다. 하지만 lo를 증가시키면 구간의 길이가 작아지므로 그 구간을 이루고 있는 숫자의 개수는 적어도 지금보다 같거나 혹은 더 적어질 것이다. 이 아이디어를 이용하면 lo와 hi를 조정해 \(\mathcal{O}(N)\)의 시간복잡도를 이용해 문제를 해결할 수 있다.

int solve() {
    int lo = 0, ans = 0, dNums = 0;
    
    for (int hi = 0 ; hi < n ; ++hi) {
        ++F[A[hi]];
        
        if (F[A[hi]] == 1) {
            ++dNums;
        }
        
        while (dNums > 2) {
            --F[A[lo]];
            
            if (F[A[lo]] == 0) {
                --dNums;
            }
            
            ++lo;
        }
        
        ans = max(ans, hi - lo + 1);
    }
    
    return ans;
}

만약 수열을 이루고 있는 수의 종류가 많아지거나, 수열의 길이가 지금보다 더 커진다면 위에서 소개한 완전 탐색과 비슷한 방법으로는 문제를 풀기 어렵지만 슬라이딩 기법을 이용하면 해결할 수 있다.