[G5] 백준 21758번 꿀 따기 C++ 그리디 알고리즘, 누적합

리뷰

 

https://www.acmicpc.net/problem/21758

문제 분류에 그리디 알고리즘이 존재하기에 정렬이 필요한가 했지만 필요 없었다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• a : 꿀의 양을 저장할 배열
• ltor : 왼쪽부터 오른쪽으로 진행하는 누적합을 저장할 배열
• rtol : 오른쪽부터 왼쪽으로 진행하는 누적합을 저장할 배열
• n : 꿀의 개수를 저장할 변수

 

함수

1. case1

int case1() {
	int mx = 0;
	for (int i = 2; i <= n - 1; ++i) {
		int val = ltor[i] - ltor[1] + rtol[i] - rtol[n];
		if (mx < val) mx = val;
	}
	return mx;
}

 

벌이 양쪽 끝에 있고, 꿀통이 중간에 있는 케이스를 탐색할 함수

 

2. case2

int case2() {
	int mx = 0;
	for (int i = n - 1; i >= 2; --i) {
		int val = rtol[1] * 2 - rtol[i] - a[i] - a[n];
		if (mx < val) mx = val;
	}
	return mx;
}

 

꿀통이 왼쪽에 있고, 오른쪽에 벌이 있는 케이스를 탐색할 함수

 

3. case3

int case3() {
	int mx = 0;
	for (int i = 2; i <= n - 1; ++i) {
		int val = ltor[n] * 2 - ltor[i] - a[i] - a[1];
		if (mx < val) mx = val;
	}
	return mx;
}

 

꿀통이 오른쪽에 있고, 왼쪽에 벌이 있는 케이스를 탐색할 함수

 

 

문제풀이

1. n값을 입력 받고, n개의 꿀 정보를 입력 받아 a배열을 초기화한다.
2. 왼쪽부터 오른쪽의 누적합을 구해 ltor배열을 초기화한다.
3. 오른쪽부터 왼쪽의 누적합을 구해 rtol배열을 초기화한다.
4. 변수 ans를 case1함수를 호출해 얻은 반환값으로 초기화한다.
5. ans와 case2함수의 반환값을 비교해 더 큰 값을 ans에 저장한다.
6. ans와 case3함수의 반환값을 비교해 더 큰 값을 ans에 저장한다.
7. ans에 저장된 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 벌통이 중간에 있는 경우는 각 벌이 양쪽 끝에 있는 경우가 가장 그리디하다.
2. 벌통이 왼쪽에 있는 경우 한 벌은 오른쪽 끝에, 나머지 벌 하나는 중간에 있는 경우가 가장 그리디하다.
3. 벌통이 오른쪽에 있는 경우 한 벌은 왼쪽 끝에, 나머지 벌 하나는 중간에 있는 경우가 가장 그리디하다.
4. 세 가지 케이스를 모두 시뮬레이션 돌려보고, 가장 큰 값을 반환하는 함수의 값을 채택하면 된다.

 

정답 코드

#include<iostream>
using namespace std;

const int N = 1e5 + 1;
int a[N];
int ltor[N + 1];
int rtol[N + 1];
int n;

int case1() {
	int mx = 0;
	for (int i = 2; i <= n - 1; ++i) {
		int val = ltor[i] - ltor[1] + rtol[i] - rtol[n];
		if (mx < val) mx = val;
	}
	return mx;
}

int case2() {
	int mx = 0;
	for (int i = n - 1; i >= 2; --i) {
		int val = rtol[1] * 2 - rtol[i] - a[i] - a[n];
		if (mx < val) mx = val;
	}
	return mx;
}

int case3() {
	int mx = 0;
	for (int i = 2; i <= n - 1; ++i) {
		int val = ltor[n] * 2 - ltor[i] - a[i] - a[1];
		if (mx < val) mx = val;
	}
	return mx;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= n; ++i) ltor[i] = ltor[i - 1] + a[i];
	for (int i = n; i >= 1; --i) rtol[i] = rtol[i + 1] + a[i];
	//cout << ltor[1] << " " << ltor[n] << " " << rtol[1] << " " << rtol[n] << "\n";
	
	int ans = case1();
	ans = max(ans, case2());
	ans = max(ans, case3());
	cout << ans;
}