프로그래머스 - 쿠키 구입

프로그래머스 - 쿠키 구입

문제를 읽고 Prefix_Sum으로 푸는 문제인 것 같아서, 해당 방식으로 풀었다.

l~m 까지의 구간은 0~m 구간 합에서 0~l 구간 합을 빼면 된다. (a)
m~r까지의 구간은 0~r 구간 합에서 0~m 구간 합을 빼면 된다. (b)
이 후 a와 b가 같을 때마다 max값을 업데이트 해준다.

결과는 답은 맞는데 효율성에서 실패했다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int prefix_sum[2002];
int solution(vector<int> cookie) {
    int answer = 0;
    int n = cookie.size();
    int total = 0;
    for(int i=0;i<n;i++) {
        prefix_sum[i + 1] = prefix_sum[i] + cookie[i];
        total += cookie[i];
    }
    total = total / 2;
    for(int i=0;i<n-1;i++) {
        for(int j=i;j<n-1;j++) {
            int a = prefix_sum[j+1] - prefix_sum[i];
            if(a > total)
                continue;
            for(int k=j+1; k<=n; k++) {
                int b = prefix_sum[k] - prefix_sum[j+1];
                if(a == b) 
                    answer = max(a, answer);
            }
        }
    }
    return answer;
}

구글링을 좀 해보니 해당 문제가 가장 긴 팰린드롬을 풀 때처럼 m을 기준으로 left_sum, right_sum을 구하면서 작은 쪽으로 증가하는 형태의 문제라는 것을 깨달았고, 해당 방식으로 풀었다.
while-loop을 멈추는 조건문만 잘 체크해주면 구현 자체는 크게 어렵지 않다.

결과는 효율성 테스트까지 통과했다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> cookie) {
    int answer = 0;
    int n = cookie.size();
    for(int i=0;i<n-1;i++) {
        int left_idx = i;
        int right_idx = i + 1;
        int left_sum = cookie[left_idx];
        int right_sum = cookie[right_idx];
        bool left_move = true;
        bool right_move = true;
        while(1) {
            answer = left_sum == right_sum ? max(answer, right_sum) : answer;
            left_move = left_idx - 1 < 0 ? false : true;
            right_move = right_idx + 1 > n - 1 ? false: true;
            if(!left_move && !right_move)
                break;
            if(right_sum > left_sum && !left_move)
                break;
            if(left_sum > right_sum && !right_move)
                break;
            if(left_sum == right_sum) {
                if(left_move) {
                    left_idx -= 1;    
                    left_sum += cookie[left_idx];
                }
                if(right_move) {
                    right_idx += 1;
                    right_sum += cookie[right_idx];
                }
                continue;
            }
            if(left_sum < right_sum && left_move) {
                left_idx -= 1;
                left_sum += cookie[left_idx];
                continue;
            } 
            if(right_sum < left_sum && right_move) {
                right_idx += 1;
                right_sum += cookie[right_idx];
                continue;
            }
        }
    }
    return answer;
}