쿠키 구입 - level 4

해결방법

이 문제는 두 아들에게 똑같은 쿠키를 줄 경우 가장 큰 쿠키의 개수를 구하는 문제이다. 아들 1에게는 N - M번째까지의 쿠키를 주었다면, 아들2에게는 M+1 - K번째까지의 쿠키를 준 쿠키가 같아야 되고 가장 큰 수를 return해야 된다. 까지의 배열에는 쿠키의 수가 임의의로 존재한다. 만약 이 문제를 경우의 수마다 합을 한다면 Time Compexity는 우주까지 간다. 그래서 배열을 이용해 M번째 까지의 합을 미리 저장해 놓는 것이 좋다. 만약 I - J까지의 합을 구하고 싶다면 J번째 합에서 I - 1번째의 합을 빼주면 된다.

 int sum[N+1];
 for (int i = 0; i < cookie.size(); ++i)
     sum[i+1] = sum[i] + cookie[i];

먼저 아들1에게 줄 쿠키를 고른다. sum[M]을 선택했다면 1 - M까지의 합이 들어있다. 그 다음 M + 1이후의 수를 선택하여 sum[M]을 빼준다면 아들 2에게는 sum[R]( M+1 <= R <= K ) - sum[M]의 수를 가지고 있을 것이다. 하지만 아들1도 1부터 시작한다는 보장이 없기 때문에 sum[M] - sum[L]( 0 <= L <= M - 1 )를 해준다.

 for(int m = 1; m < cookie.size(); ++m) {
     int c = sum[m]; // 1 - M 아들1의 쿠키의 수
     for(int r = m+1; r <= cookie.size(); ++r) {
         int s = sum[r] - c; // M + 1 - r 아들2의 쿠키의 수
         if(answer >= s || s > c) continue;
         for(int l = 0; l < m; ++l) // sum[l]을 빼주어 아들1의 쿠키의수를 l - M으로 바꾸어준다.
            if(s == c - sum[l]) { // 만약 같다면
                answer = max(answer, s); // 최대 쿠키의 수를 대입한다.
                break;
            }
    }
}

조사하면서 조건에 맞는 최대 쿠키의 수를 대입해준다.

전체코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int sum[2001];
int solution(vector<int> cookie) {
    int answer = 0;
    for (int i = 0; i < cookie.size(); ++i)
        sum[i+1] = sum[i] + cookie[i];
    for(int m = 1; m < cookie.size(); ++m) {
        int c = sum[m];
        for(int r = m+1; r <= cookie.size(); ++r) {
            int s = sum[r] - c;
            if(answer >= s || s > c) continue;
            for(int l = 0; l < m; ++l)
                if(s == c - sum[l]) {
                    answer = max(answer, s);
                    break;
                }
        }
    }
    return answer;
}

[출처] https://programmers.co.kr/learn/courses/30/lessons/49995?language=cpp