문제

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

윤호는 퍼주기로 유명한 편의점 사장이다. 그의 편의점에는 특이한 임금 체계를 가지고 있다.

• 각 날마다 일의 차이 때문에 일마다 급여가 정해져 있다.
• 윤호는 오차 없이 일급을 따박 따박 당일에 준다.
• 정해진 일의 수만큼만 일을 시킨다.
• 한번이라도 퇴직한 자를 다시 취직 시키지 않는다. (만약 취직을 한다면, 일을 시작한 날부터 끝날 때까지 하루도 빠지면 안 된다.)

무서운 아르바이트를 짤린 준수는 n+1일 후에 001에 월세를 내야 해서 윤호가 사장으로 있는 편의점에 취직하려 한다. 다행히 주변 퇴직자들의 얘기로 급여에 관련해 파악했다. 또한 퇴직자들의 급여 통계를 통해 당장 n일 후까지 일급 정보를 알아냈다. 하지만 준수는 시험을 준비해야 하기에 최대 m일 밖에 일을 할 수 없다.

어제까지 과제를 제출하고 지금도 001에서 자고 있는 준수를 위해, 코딩 잘하는 여러분이 일을 해서 벌 수 있는 최대 이익을 준수에게 또 알려주도록 하자.

입력

월세를 내기 바로 전 날까지인 n (1 ≤ n ≤ 100,000) 일과 일을 할 수 있는 날 m (0 ≤ m ≤ n) 일이 주어진다.

그 다음 줄에는 1일부터 n일까지의 일급 Ti가 순서대로 주어진다. (0 < Ti ≤ 1,000,000)

출력

준수가 일을 해서 벌 수 있는 최대 이익을 출력한다.

예제

---

풀이과정

완전 탐색 (시간 초과)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll; // 일급이 최대 100만이므로 그 합은 long long형 

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

	int n;
	cin >> n; // 월세 내기 전까지 주어진 날 (최대 10만)

	int m;
	cin >> m; // 일할 수 있는 날 (0 <= m <= n)

	vector<int> v(n);
	for(int i = 0; i < n; i++){
		cin >> v[i]; // 일급 (최대 100만) 
	}

	vector<ll> v1;
	
	// n일 중에 'm일 연속' 일할 수 있을 때, 
	// 준수가 받을 수 있는 최대 이익은?  
	for(int i = 0; i <= n - m; i++){ 
		ll sum = 0;
		// m일 연속 일했을 때 받을 수 있는 이익 
		for(int j = i; j < i + m; j++){ 
			sum += v[j]; 
		}
		v1.push_back(sum); 
	}
	
	ll max = *max_element(v1.begin(), v1.end());
	cout << max << endl;
	
	return 0;
}

슬라이딩 윈도우

https://velog.io/@bestcoders/백준-12847번-꿀-아르바이트

1. 문제에 주어진 최대 크기의 배열을 선언하고, 입력에 주어진 일급을 순서대로 넣는다.
2. 준수는 m일 연속으로 일해야 하므로 1일부터 일급을 더한다. 최대 m일 더해줬다면, m일을 초과하는 인덱스부터는 가장 낮은 인덱스의 일급을 빼주고 다음 위치의 일급을 더한다.
3. 최댓값을 구한다.

#include <iostream>
using namespace std;

int n, m;
long long ans = 0; // 일급이 최대 100만이므로 그 합은 long long형 
int arr[100'001];

int main() {
    cin >> n >> m; // 최대 10만 

    for (int i = 1; i <= n; i++) {
        cin >> arr[i]; // 최대 100만 
    }
    
    long long sum = 0; 
    for (int i = 1; i <= n; i++) {
        if (i > m) {
            sum -= arr[i - m]; // 슬라이딩 윈도우 
        }
        sum += arr[i]; 
        ans = max(ans, sum);
    }
	
    cout << ans;
	
    return 0;
}