쿠키 구입

문제 설명

과자를 바구니 단위로 파는 가게가 있습니다. 이 가게는 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

---

문제 해설

 

최대값과 죄소값이 유동적으로 변하는 이진탐색이라고 생각하면 된다. 그렇지만, 유동적으로 변하는 최댓값과 최솟값으로 인해 동적으로 전체탐색을 해야함으로, 이진탐색 알고리즘을 사용할수는 없다!

 

0번부터 최대배열쿠키 위치까지 배열순환을 하면서, 탐색을 하는데 지정된 위치부터 형과 동생의 쿠키이동범위까지 이동시키면서 중첩덧셈을 하면된다.

 

그렇게 하다가 최댓값까지 이동하거나 최댓값을 찾게되면( 두 형제가 쿠키를 나누어먹어야 하기 때문에 최댓값은 전체쿠키의 반이다. )

 

해당 최댓값을 배열에 넣거나 반환해주면 된다.

 

자세한 설명은 다음 링크 참조 이분이 설명을 잘해주셨다.

https://school.programmers.co.kr/questions/32966

프로그래머스

---

첫 번째 시도

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> cookie)
{
    int begin = 0;
    int end = cookie.size();

    while (begin <= end)
    {
        int middle = (begin + end) * 0.5;

        int A, B;
        A = B = 0;

        for (int i = begin; i <= middle; i++)
            A += cookie[i];
        for (int i = middle+1; i < end; i++)
            B += cookie[i];
        if (A == B) return cookie[A];

        else if (cookie[middle] < (A + B) * 0.5)
            begin++;
        else
            end--;
    }

    return 0;
}

실패

 

이진트리 방식으로 접근을 시도하였지만, 최댓값과 최솟값이 유동적으로 변하고, 해당 중심위치에서 찾은 쿠키개수가 가장 최고의 쿠키개수가 아닐 수 있기 때문에 틀리다.

---

두 번째 시도

#include <string>
#include <vector>
#include <set>

using namespace std;

int solution(vector<int> cookie)
{
    set<int> result;
    for (int i = 0; i < cookie.size(); i++)
    {
        int Amovepoint = 1;
        int Bmovepoint = 0;
        while (true)
        {
            int A = 0;
            if(i - Amovepoint >= 0)
                for (int j = 1; j <= Amovepoint; j++)
                    A += cookie[i - j];

            int B = 0;
            if (i + Bmovepoint < cookie.size())
                for (int j = 0; j <= Bmovepoint; j++)
                    B += cookie[i + j];

            if ((A != 0 || B != 0) && A == B)
                result.insert(A);
            else if (A == 0 || B == 0)
                break;

            if (A < B && i - Amovepoint >= 0)
                Amovepoint++;
            else if (i + Bmovepoint < cookie.size())
                Bmovepoint++;
        }
    }

    if(result.size() > 0)
        return *result.rbegin();
    return 0;
}

실패

 

이번에는 그냥 데이터를 전체순환하게 하였다. 전체 순환을 진행하면서 내가찾은 중심값이 최대쿠키값인지는 모르겠으니까 전부다 박아넣고 최종값에서 가장 큰 값을 반환하게 하였다.

 

그런데 시간초과로 오버되었다.

---

세 번째 시도

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int solution(vector<int> cookie)
{
    set<int> result;
    result.insert(0);

    int Max = 0;
    for (auto& def : cookie)
        Max += def;
    Max *= 0.5;

    for (int i = 1; i < cookie.size(); i++)
    {
        int Amovepoint = 0;
        int Bmovepoint = 0;

        int A = 0;
        int B = cookie[i];
        while (true)
        {
            if (A == B) 
                result.insert(A);

            if (A < B && i - Amovepoint > 0) {
                Amovepoint++;
                A += cookie[i - Amovepoint];
            }
            else if (i + Bmovepoint < cookie.size() - 1) {
                Bmovepoint++;
                B += cookie[i + Bmovepoint];
            }
            else break;
        }
        if (*result.rbegin() >= Max) return *result.rbegin();
    }

    return *result.rbegin();
}

성공

 

좀더 직관적으로 다가가기로 했다. 시간초과가 나타나니까 굳이 사용할 필요 없는 알고리즘을 전부다 빼버렸다.

 

그리고, 순환중 전부다 한번씩 다시 더할 필요가 없이 그냥 데이터를 한개씩 더해가면서 탐색해나가도 값의 차이가 나지 않는다는걸 깨달았다.

 

시간초과를 해결해서 성공했다.