문제 푼 날짜 : 2021-10-06

문제

문제 링크 : https://www.acmicpc.net/problem/12847

접근 및 풀이

슬라이딩 윈도우 알고리즘을 이용하는 문제였다.

코드는 아래의 생각대로 구현하였다.

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

코드

// 백준 12847번 : 꿀 아르바이트
#include <iostream>

using namespace std;

int n, m;
long long ans = 0;
int arr[100001];

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    
    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;
}

결과

피드백

입력 범위 체크 잊지말자