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

문제 설명

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

---

C++ 풀이

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> cookie) {
	int max = 0;
	int fson, sson = 0;
	int sum[2000]; int halfsum;
	sum[0] = cookie[0];
	for (int i = 1; i < cookie.size(); i++) //1부터 i번 바구니까지의 과자 개수 합 저장
		sum[i] = sum[i - 1] + cookie[i];
	halfsum = sum[cookie.size() - 1] / 2; //전체 과자 개수의 반
	for (int f = 0; f < cookie.size() - 1; f++) {
		for (int g = 1; g < cookie.size() - f; g++) {
			if (f == 0)
				fson = sum[f + g - 1];
			else
				fson = sum[f + g - 1] - sum[f - 1];
			if (fson > halfsum) //첫째 아들 과자 개수가 전체 개수의 반을 초과하였는지 확인
				break;
			if (fson > max) { //첫째 아들의 과자 개수가 현재 max값보다 큰 값일 경우에만 확인
				for (int i = f + g; i < cookie.size(); i++) {
					sson = sum[i] - sum[f + g - 1];
					if (sson >= fson) {
						if (fson == sson) //첫째 아들과 둘째 아들의 과자 개수가 같을 경우 max 갱신
							max = fson;
						break;
					}
				}
			}
		}
	}
	return max;
}

 

1부터 N까지의 바구니에 담긴 과자의 합을 sum[N]에 미리 저장하였다.

sum[]을 이용하여 for문 내에서 두 아들의 과자 수가 같은지 확인하였다.

 

효율성 테스트 6,7,8이 실패로 떠서 추가적으로 다음 두가지 조건을 체크하였더니 통과할 수 있었다.

• 첫째 아들이 전체 과자의 반을 넘게 가진 경우 -> 첫째 아들과 둘째 아들은 같은 개수의 과자를 가질 수 없다
• max가 될 가능성이 있는 과자 개수인가 -> 조건에 부합하는 최대 과자 수를 구하는 것이 목표이기 때문이다

 

 

 

 

 

문제 링크

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

코딩테스트 연습 - 쿠키 구입 | 프로그래머스