[BOJ] 백준 15360 Rasvjeta

문제 링크

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

15360번: Rasvjeta

 

하나의 가로등은 그 지점과 양쪽으로 K만큼 떨어진 지점까지 불을 밝힙니다.

앞에서부터 순서대로 보면서 빛이 안 들어오는 지점이 있다면 그 지점에서 뒤로 K 번째 지점에 가로등을 설치하면 됩니다.

 

이유는 다음과 같습니다.

위의 방법으로 처리하던 중에 어떤 지점 X가 어둡다는 뜻은, X를 보고 있는 상황에서 적어도 X 앞의 모든 지점은 불이 밝혀져 있다는 뜻입니다. 그럼 이왕 X를 밝힐 거면 밝을 것이 확실한 지점(X 앞의 지점들)을 제외하고 최대한 불을 비추는 게 이득이므로 X를 밝힐 수 있으면서 가장 멀리 떨어진 지점인 (X + K) 지점에 가로등을 설치하게 됩니다.

 

 

정답 코드

#include <iostream>
using namespace std;
 
int n, m, k;
int ans;
int p[2000];
void foo(int x) {
    for (int i = x - k; i < x + k + 1; i++){
        if(i < 1) continue;
        if(i > n) break;
        p[i] = 1;
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        foo(x);
    }
    for (int i = 1; i < n + 1; i++) {
        if (p[i] == 0) {
            ans++;
            if (i + k < n + 1) {
                i += k;
                foo(i);
            }
        }
    }
    cout << ans;
}