프로그래머스/윈터코딩2018기출/쿠키구입/C++

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

알고리즘 연습 - 쿠키 구입 | 프로그래머스

 

m번째 바구니를 기준(시작점)으로 두 아들이 m번째 바구니부터 각각 좌우로 순회하면서 쿠키 갯수를 서로 더해가면서 양아들의 쿠키갯수가 같아지면서 동시에 이것이 최대값일 경우 max값을 갱신해주는 방식으로 코드를 구현할 수 있다. 

시간 초과가 걸리는 문제가 있는데, 중간에 주석으로 달아놓은 설명대로 break를 사용하여 불필요한 순회를 하지 않는다면, 효율성 테스트 케이스 부분까지 모두 통과할 수 있다. 

---

[구현코드_C++로 구현]

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(vector<int> cookie) {
    int answer = -1;
    int max = 0;
    for(int m = 1; m < cookie.size(); m++){
        int leftSum = 0;
        for(int j = m-1; j >= 0; j--){
            int rightSum = 0;
            leftSum += cookie[j];
            if(leftSum < max) continue; // 왼쪽 아들의 쿠키 갯수가 기존의 max보다 낮다면, 굳이 오른쪽 아들의 쿠키 갯수를 헤아릴 필요 없음
            for(int k = m; k < cookie.size(); k++){
                rightSum += cookie[k];
                if(leftSum == rightSum && leftSum > max){ // 새로운 Sum이 기존 max 보다 큰 경우에만 max값에 갱신해준다.
                    max = leftSum;
                    break;
                }
                if(rightSum > leftSum) break; // 오른쪽 아들의 쿠키갯수가 왼쪽아들의 쿠키갯수를 넘어가는 경우 더 세지 말고 루프를 탈출
            }
        }
    }
    answer = max;
    return answer;
}
int main(){
    cout<<solution({1,1,2,3});
    return 0;
}