[프로그래머스][level4] 쿠키 구입 (C++)

https://programmers.co.kr/learn/courses/30/lessons/49995

코딩테스트 연습 - 쿠키 구입

 

 

[난이도] level4
[유형] 이분탐색

[풀이]
N이 2000이므로 O(N^3)까지 가게되면 시간초과가 납니다.
O(N^2)이나 O(N^2logN) 알고리즘이 필요합니다.

아래 코드는 부분합+이분탐색을 이용하여 O(N^2logN) 으로 해결하였습니다.
다른 분들은 보통 투포인터를 이용한 O(N^2)으로 푼것 같습니다.

풀이는 일단 구간합 배열을 만들고 시작합니다.
sum[i] : 1~N까지 모든 원소들의 합.

그 뒤 첫번째 아들이 선택할 수 있는 모든 구간 (i~j)에 대해 둘째 아들이 선택할 수 있는 (j+1~k)가 있는지를 구할 것입니다.

구간합 배열을 이용해 sum(i,j)는 sum[j]-sum[i-1]로 구할 수 있습니다.
이제 sum[j]-sum[i-1]와 동일한 값을 같는 sum(j+1,k)를 찾아야 하는데 lower_bound(이분탐색)를 이용해 찾을 수 있습니다.

부분합 배열에서 sum(j+1,k)가 존재하는지를 찾으려면 sum[j] + sum[j] - sum[i-1] 을 lower_bound를 이용해서 찾으면 됩니다.

위의 식이 나온 이유는 아래와 같습니다.

        첫째아들   둘째아들
1+2+...[i+..+j] / [(j+1)+..+k] = sum(j+1,k)
                     [i+..+j]       = sum(i,j)

위와 같이 sum(j+1,k)와 sum(i,j)가 같아야 하기 때문에 1~j까지의 합 sum[j]에 sum(j+1,k) 인 (sum[j] - sum[i-1])를 더한 값이 부분합 배열에 존재하면 sum(j+1,k) == sum(i,j) 가 만족되어 각 아들이 가진 과자 수 sum[j] - sum[i-1]가 정답의 후보가 될 수 있습니다.

이 후보들을 이용해 최댓값을 갱신해 주면 최종 답을 구할 수 있습니다.

 

#include <vector>
#include <algorithm>
using namespace std;
int N,answer;
int solution(vector<int> cookie) {
    N=cookie.size();
    cookie.insert(cookie.begin(),0);
    vector<int> sum(N+1);
    for(int i=1;i<=N;i++) sum[i]=sum[i-1]+cookie[i];
    for(int i=1;i<=N-1;i++){
        for(int j=i;j<=N-1;j++){
            int t = 2*sum[j]-sum[i-1];
            int idx = lower_bound(sum.begin(),sum.end(),t)-sum.begin();
            if(idx<=N && sum[idx]==t) answer=max(sum[j]-sum[i-1],answer);
        }  
    }
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/쿠키_구입.cpp