문제 푼 날짜 : 2021-10-06

문제

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

접근 및 풀이

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

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

1. 문제에 주어진 최대 크기의 배열을 선언하고, 얼음이 있는 위치에 입력값을 넣어준다.
2. 백곰 앨버트는 자리잡은 곳에서 좌우로 K씩 먹는다고 하였으니, 최초 2*K 만큼 커버할 수 있다.
3. 처음부터 배열의 값들을 더해주다가, 2*K + 1 부터 인덱스가 가장 낮은 위치의 값을 빼주고 다음 위치의 값을을 추가해준다. 이 때, 더한 값의 최댓값을 업데이트해준다.

코드

// 백준 10025번 : 게으른 백곰
#include <iostream>

using namespace std;

int N, K, ans;
int arr[1000001];

int main() {
    cin >> N >> K;

    for (int i = 0; i < N; i++) {
        int g, x;
        cin >> g >> x;
        arr[x] = g;
    }

    K = 2 * K + 1;
    int sum = 0;
    for (int i = 0; i <= 1000001; i++) {
        if (i >= K) {
            sum -= arr[i - K];
        }
        sum += arr[i];
        ans = max(ans, sum);
    }
    cout << ans;
    return 0;
}

결과

피드백

언제나 입력값에 대한 범위체크는 꼼꼼히하고 구현하도록 하자.