프로그래머스] C++ 쿠키 구입(Level 4)

 

 

해당 문제는 프로그래머스에서 푸실 수 있습니다.

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

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

 

 

1. 문제

과자를 바구니 단위로 파는 가게가 있습니다.

이 가게는 1번부터 N번까지 차례로 번호가 붙은 바구니 N개가 일렬로 나열해 놨습니다.

철수는 두 아들에게 줄 과자를 사려합니다.

첫째 아들에게는 l번 바구니부터 m번 바구니까지,

둘째 아들에게는 m+1번 바구니부터 r번 바구니까지를 주려합니다.

단, 두 아들이 받을 과자 수는 같아야 합니다(1 <= l <= m, m+1 <= r <= N).

즉, A[i] 를 i번 바구니에 들어있는 과자 수라고 했을 때, A[l]+..+A[m] = A[m+1]+..+A[r] 를 만족해야 합니다.

각 바구니 안에 들은 과자 수가 차례로 들은 배열 cookie가 주어질 때,

조건에 맞게 과자를 살 경우 한 명의 아들에게 줄 수 있는 가장 많은 과자 수를

return 하는 solution 함수를 완성해주세요. (단, 조건에 맞게 과자를 구매할 수 없다면 0을 return 합니다)

 

제한사항

• cookie의 길이는 1 이상 2,000 이하입니다.
• cookie의 각각의 원소는 1 이상 500 이하인 자연수입니다.

 

 

입출력 예

cookie	result
[1,1,2,3]	3
[1,2,4,5]	0

 

입출력 예 설명

 

입출력 예 #1

첫째 아들에게 2, 3번 바구니를, 둘째 아들에게 4번 바구니를 사주면 두 아들은 각각 과자 3개를 받습니다.

 

입출력 예 #2

주어진 조건에 맞게 과자를 살 방법이 없습니다.

 

 

2. 풀이

해당문제는 프로그래머스의 가장 긴 팰린드롬 문제와 비슷합니다.

programmers.co.kr/learn/courses/30/lessons/12904

 

다른점은 왼쪽의 합들과 오른쪽의 합들 값이 같을 때, 최대 합을 구하는 점이 다릅니다.

 

그리고 문제대로 연속된 수의 합이기 때문에 생각해야할 조건이 많아짐니다.

 

이를 한방에 해결할 방법이 있으니 바로 i 값을 기준으로 범위를 양 옆으로 넓혀가는 방법입니다.

 

이렇게 구해주면 왼쪽과 오른쪽 값이 같을 때, 최대 합을 구할 수 있습니다.

 

왜냐하면, 문제는 같은 쿠키를 나눠줄 수 있는 최대 개수를 구하는 문제이기 때문입니다.

 

때문에 저희는 i 값을 기준으로 왼쪽과 오른쪽이 경계를 벗어나지 않도록 예외처리만 해주면 문제는 쉽게 풀립니다.

 

 

 

 

3. 코드

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

using namespace std;

int solution(vector<int> cookie) {
    int answer = 0;

    for(int i = 0; i < cookie.size() - 1; i++){
        int left_sum = cookie[i];
        int right_sum = cookie[i + 1];
        int l_idx = i;
        int r_idx = i + 1;

        while(true){

            if(left_sum == right_sum)
                answer = max(answer, left_sum);

            if(left_sum > right_sum){
                if(r_idx + 1 == cookie.size()) break;
                right_sum += cookie[++r_idx];
            }
            else{
                if(l_idx - 1 < 0) break;
                left_sum += cookie[--l_idx];
            }            

        }
    }

    return answer;
}