[프로그래머스] 쿠키 구입

문제 설명

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

---

풀이

60분 이상
걱정만 많고 생각은 짧았던 창피한 풀이이다. 아무래도 Level 4의 문제이기 때문에 당연히 어려울거라 생각하여 그냥 문제 그대로 구현할 생각을 못했었다. 사실 이렇게 풀거면 dp를 쓸 것도 없이 0~n-1 사이의 m값을 고정해놓고 양쪽으로 더해가며 푸는게 더 나은 코드일 것이다.
‘DP로 풀어야겠다’라고 생각한 다음 풀이를 더 깊게 생각하지 않고 달려들어 풀었던 것이 큰 실수였다. 다시 풀어낸 코드로는 훨씬 빠른 효율성으로 통과할 수 있었다.

코드

// 10:14 ~ 11:30
#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(vector<int> cookie) {
    int answer = 0;
    int n = cookie.size();
    int dp[2000][2000] = {0,};
    
    for(int i =0; i < n; ++i){
        dp[i][i] = cookie[i];
    }
    
    for(int j = 1; j < n; ++j){
        for(int i = 0; i < j; ++i){
            dp[i][j] = dp[i][j - 1] + dp[j][j];
        }
    }
    
    for(int m = 0; m < n; ++m){
        int l = m;
        int r = m + 1;
        while(true){
            if(l < 0 || r >= n) break;
            
            if(dp[l][m] > answer && dp[l][m] == dp[m+1][r]){
                answer = dp[l][m];
            }
            
            if(dp[l][m] > dp[m+1][r]) ++r;
            else --l;
        }
    }
    return answer;
}

다른 풀이

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

using namespace std;

int solution(vector<int> cookie) {
    int answer = 0;
    int n = cookie.size();
    
    for(int m = 0; m < n - 1; ++m){
        int l = m, lsum = cookie[m];
        int r = m + 1, rsum = cookie[m + 1];
        
        while(true){
            
            if(lsum > answer && lsum == rsum){
                answer = lsum;
            }
            
            if(lsum > rsum){
                ++r;
                if(r >= n) break;
                rsum += cookie[r];
            } 
            else{
                --l;
                if(l < 0) break;
                lsum += cookie[l];
            }
        }
    }
    return answer;
}