백준 12847 꿀 아르바이트 C++ 풀이

총 일할 수 있는 N일 중에서 연속된 M일을 선택했을 때 그 부분합이 최대가 되는 경우를 계산하는 문제이다.

구간을 정해서 부분합을 구하는 슬라이딩 윈도우 혹은 투포인터 알고리즘을 적용할 수 있고, 여기서는 M이라는 일정한 크기의 윈도우가 정해져있으므로 슬라이딩 윈도우 알고리즘을 사용하여 풀이한다.

https://ji-musclecode.tistory.com/37

슬라이딩 윈도우 알고리즘(Sliding Window) (feat. 투 포인트)

 

소스 코드

#include <iostream>
#include <vector>
using namespace std;
#define MAX 100001

int main() {
	int n; cin >> n; // 월세 내기까지 남은 일 수	
	int m; cin >> m; // 최대 일할 수 있는 일 수
	long long arr[MAX] = {0,}; // 일급
	for (int i = 1; i < n + 1 ; i++) { // 1부터 n일까지의 일급 저장
		cin >> arr[i]; 
		arr[i] = arr[i - 1] + arr[i]; // 해당 인덱스까지의 수열의 합을 기록한다. 
	}

	// 5 3 
	// 10 20 30 20 10

	// arr : 10 30 60 80 90

	long long max = 0;  // 부분합

	// 부분합이 최대가 되는 경우 
	for (int i = 0; i < n - m + 1; i++) {
		long long sum = arr[i + m] - arr[i]; 
		if (sum > max)
			max = sum;
	}
	cout << max << endl;

	return 0;
}

 

설명

(1) arr[i] 입력과 동시에  수열의 합을 기록한다. 주석을 보면, arr의 최종 결괏값은 해당 인덱스에서 그 앞의 값을 더한 값으로 계산된다. 

(2) max값을 0으로 설정하고 처음부터 n - m까지 접근해 sum값을 순차적으로 구한다. 이때 sum값은 특정 간격에서의 sum 값이므로, arr에서 처음과 끝의 값을 빼주면 된다. 

(3) max 값이 새로 구한 sum보다 작으면 sum을 새롭게 설정한다. 

 

실수할 수 있는 포인트

(1) arr와 max, 그리고 sum은 int가 아닌 long long 타입으로 설정해야 함.

(2) 두 번 탐색하기 위해 이중루프를 사용하면 시간초과 에러가 발생한다.