[ 프로그래머스 쿠키 구입 (Lv4) ] (C++)

프로그래머스의 쿠키 구입(Lv4) 문제이다.

[ 문제풀이 ]

두 명의 아들이 같은 과자 수를 받도록 과자를 나눠줄 때, 한 명에게 줄 수 있는 가장 많은 과자 수를 구해야 하는 문제이다.

본인은 모든 과자를 '기준점'으로 고려해서 문제를 접근해보았다.

예를 들어서 { 1, 2, 3, 4 } 로 과자가 주어졌다고 가정해보자.

본인이 위에서 말했던 '기준점'은 하나를 선택함에 따라 자연스럽게 또 하나의 기준점이 생기게 된다.

가장 첫 번째 값을 기준점으로 삼았다고 생각해보자.

그럼 기준점은 '1'의 값을 가지고 있는 과자가 될 것이다. 이게 바로 "첫째 아들에게 과자를 줄 기준점"이 된다.

이 값을 기준점으로 선택함에 따라서 또 하나의 기준점은 (i + 1)번째 값, 즉, 두 번째 값인 '2'가 "둘째 아들에게 과자를 줄 기준점" 이 된다.

이렇게 나눈 이유는 다음과 같이 문제를 풀어나가기 위해서이다.

.

위와 같이 과자를 나눠주기 위해서이다.

하나의 기준점1, 즉, "첫째 아들에게 과자를 줄 기준점"을 설정하게 되면, 그 이후로 첫 째 아들에게 줄 과자는, "기준점보다 상대적으로 더 앞에 있는 값들" 만 추가적으로 줄 것이다. 반대로, 기준점1에 의해서 기준점2가 자연스럽게 설정된다면, 둘째 아들에게 줄 과자는 "기준점2보다 상대적으로 뒤에 있는 과자들"만 추가적으로 줄 것이다.

지금부터 첫째아들에게 과자를 주기 위한 기준점을 기준점1.

둘째아들에게 과자를 주기 위한 기준점을 기준점2.(기준점1 + 1번 Index) 로 이야기하겠다.

다시 본론으로 돌아와서 { 1, 2, 3, 4 } 로 돌아와보자.

기준점1을 0번 Index로 설정하면, 기준점2는 1번 Index가 된다.

그 값을 계산해본다면, 첫째 아들에게 주는 과자의 갯수 = 1개.

둘째 아들에게 주는 과자의 갯수 = 2개가 된다.

그럼, 이 상황에서는 누구에게 과자를 추가적으로 더 줘야 두 아들에게 줄 수 있는 과자의 수를 맞출 가능성이 있을까 ?

딱 봐도 첫째 아들이다. 이미 둘째 아들이 가진 과자의 수가 더 많은데, 여기서 굳이 둘째 아들에게 추가적으로 과자를 더 준다면, 절대로 과자의 수를 맞출 가능성이 없어지게 된다.

즉 ! 이런 경우에는 첫째 아들에게 과자를 추가적으로 줘야 한다. 위에서 말했듯이 첫째 아들에게는 "기준점보다 상대적으로 더 앞에 있는 과자들"만 추가적으로 줄 수 있다. 그런데 ? 이미 0번 Index이기 때문에 첫째 아들에게 줄 수 있는 과자가 더 이상 존재하지 않는다. 즉 ! 0번 Index는 좋은 기준점이 아니였다.

1번 Index를 기준점1로 삼아보자.

그럼 현재, 첫째 아들에게 주는 과자의 수 = 2개. 1번 Index가 기준점1이 됨에 따라서, 기준점2는 자연스럽게 2번 Index가 되고, 둘째 아들에게 주는 과자의 수 = 3개 가 된다.

또 비교를 해보자. 이미 둘째 아들이 더 과자를 많이 받고 있는 상황이다. 그럼 ? 당연히 첫째 아들에게 과자를 더 줘야 한다. 그럼 과자를 더 줘보자. 1번 Index이기 때문에 줄 수 있는 과자가 0번 Index가 있다. 과자를 주게 되면 첫째 아들은 2 + 1 = 3개의 과자를 받게 되고, 둘째 아들 또한 3개의 과자를 받게 된다. 드디어 같은 과자의 수가 처음 등장했다. 그럼, 기존의 정답과 비교해서 정답을 Update해준다.

이런식으로 마지막 Index까지 비교를 해주는 것이다.

위에서 한 이야기를 정리해서 이야기해보면 다음과 같다.

1. 기준점1을 선택한다. (선택하는 순간 동시에 기준점2 (기준점1 + 1)가 선택된다.)

2. 첫째 아들에게는 기준점1로 부터 상대적으로 앞에 있는 값들만 추가적으로 과자를 줄 것이고,

    둘째 아들에게는 기준점2로 부터 상대적으로 뒤에 있는 값들만 추가적으로 과자를 줄 것이다.

3. 현재 두 아들이 받을 수 있는 과자의 수를 비교해서 "더 적은 과자를 받은 아들 에게 추가적으로 과자를 지급" 할 것이다.

[ 소스코드 ]

#include <string>
#include <vector>
 
using namespace std;
 
int Bigger(int A, int B) { if (A>B) return A; return B; }
 
int solution(vector<int> cookie)
{
    if (cookie.size() == 1) return 0;
    if (cookie.size() == 2)
    {
        if (cookie[0] == cookie[1]) return cookie[0];
        return 0;
    }
 
    int answer = 0;
    for (int i = 0; i < cookie.size() - 1; i++)
    {
        int First_Idx = i;
        int Second_Idx = i + 1;
        int First_Sum = cookie[First_Idx];
        int Second_Sum = cookie[Second_Idx];
 
        while (1)
        {
            if (First_Sum == Second_Sum) answer = Bigger(answer, First_Sum);
 
            if (First_Idx > 0 && First_Sum <= Second_Sum)
            {
                First_Idx--;
                First_Sum = First_Sum + cookie[First_Idx];
            }
            else if (Second_Idx < cookie.size() - 1 && Second_Sum <= First_Sum)
            {
                Second_Idx++;
                Second_Sum = Second_Sum + cookie[Second_Idx];
            }
            else break;
        }
    }
    return answer;
}