BOJ 32069. 가로등

문제 링크 

 

문제 풀이

  이 문제는 수직선 위에서 가로등의 위치들이 주어질 때 각 수직선 상의 위치마다 밝기를 작은 것부터 $K \leqslant 3\times 10^5$개 출력하는 문제이다. 

 

 일단 $ L \leqslant 10^{18} $ 이므로 배열에 각 위치들을 배열에 저장하거나, 완전탐색을 할 경우 MLE나 TLE가 날 수밖에 없다. 그래서 필요한 위치들의 밝기만 저장하거나 다른 방법이 필요하다.

 

 가장 처음에 생각했던 것은 인접한 가로등 사이의 구간 길이를 저장하는 것이다. 구간의 길이의 개수는 항상 $N+1$개이고, $N \leqslant 3\times 10^{5} $ 이기 때문에 완전탐색을 해도 별 문제가 없고, 구간의 길이가 각 위치들의 밝기를 특정해주기 때문이다. 예를 들어서 구간의 길이가 5라고 하면 밝기는 아래와 같이 특정된다.

위치	x	x+1	x+2	x+3	x+4	x+5	x+6
밝기	0	1	2	3	2	1	0
가로등이 있는가?	O						O

 

 조금 더 구체적으로 써보면

let) 구간 길이 x
if  x % 2 == 0  $\Rightarrow$ 밝기 1 ~ $\frac{x}{2}$ 2개씩 존재
else if x % 2 == 1 $\Rightarrow$ 밝기 1 ~ $\frac{x-1}{2}$ 2개씩 존재 + 밝기 $\frac{x+1}{2}$ 1개 존재

 

추가적으로 위치 0부터 최초의 가로등까지의 구간이나 마지막 가로등부터 위치 $L$까지의 구간은 따로 고려해줘야하는데 이때는 구간의 길이가 k이면 그 구간에 밝기 1 ~ k까지 1개씩 존재한다.

 

 이제 이것을 이용해서 밝기 1인 칸의 개수, 밝기 2인 칸의 개수, ... 등을 알면 된다. 이를 수식으로 써보자.

 

let) $L_{k}$ = (밝기가 k인 칸의 개수)

let) $I_{x}$ = (구간의 길이가 x인 구간의 개수)

let) $X_{0} = A[0]$

let) $X_{1} = L - A[N-1]$

$$ L_{k} = I_{2k-1}\space + 2\sum_{i\geq2k}I_{i} + \begin{cases}2 & {X_{0},X_{1}\geq k}\\1 & {X_{i}\geq k\space and \space X_{1-i}<k\space(i\in{0,1})}\\0 & {X_{0},X_{1}< k}\end{cases} $$

 

 이제 밝기 k를 1부터 높여가며 차례대로 확인하고 지금까지 출력한 개수가 $K$개가 되면 종료해주면 된다. 시간복잡도는 밝기가 최대 K까지 있을 수 있기 때문에 $O(K)$만큼 반복문을 수행하고, 반복문 안에서 lowerbound를 찾는 과정이 $O(logN)$ 이므로 전체는 $O(KlogN)$ 이다.

 

P.S.) 문제 풀 땐 생각을 못했는데 가로등들을 기준으로 BFS를 수행해줘서 푸는 게 정풀이라고 한다,,

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const ll LMAX = 1000000000000000000;
const int NMAX = 300000, KMAX = 500000;
ll L, A[NMAX + 10], inter[NMAX + 10];
int N, K;

void input() {
    cin >> L >> N >> K;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
}

void init() {
    inter[0] = A[0];          
    inter[1] = L - A[N - 1]; 
    for (int i = 2; i <= N; i++) {
        inter[i] = A[i - 1] - A[i - 2] - 1;  
    }
    sort(inter + 2, inter + N + 1); 
}

void solve() {
    if (N >= K) {
        for (int i = 0; i < K; i++) cout << 0 << "\n"; 
        return;
    } else {
        for (int i = 0; i < N; i++) cout<<0<<"\n";
        K -= N;
        int K_prime = K;
        for (ll i = 1; i <= 2*K; i+=2) {
            ll n = (i + 1) / 2;
            if (inter[0] >= n && i%2==1) {
                cout<<n<<"\n"; K_prime--;
                if (K_prime == 0) return;
            }
            if (inter[1] >= n && i%2==1) {
                cout << n << "\n"; K_prime--;
                if (K_prime == 0) return;
            }
            int lb = lower_bound(inter + 2, inter + N + 1, i) - inter;
            if(lb>=N+1) continue;
            if (inter[lb] == i) {
                int lbprime = lower_bound(inter + 2, inter + N + 1, i + 1) - inter;
                for (int j = lb; j < lbprime; j++) {
                    if (K_prime == 0) return;
                    cout << n << "\n"; K_prime--;
                }
                for (int j = lbprime; j <= N; j++) {
                    if (K_prime == 0) return;
                    cout << n << "\n"; K_prime--;
                    if (K_prime == 0) return;
                    cout << n << "\n"; K_prime--;
                }
            } else {
                for (int j = lb; j <= N; j++) {
                    if (K_prime == 0) return;
                    cout << n << "\n"; K_prime--;
                    if (K_prime == 0) return;
                    cout << n << "\n"; K_prime--;
                }
            }
        }
    }
}

int main() {
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    input();
    init();
    solve();
}