백준 12003 Diamond Collector (USACO US Open 2016 Silver 2번)

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

12003번: Diamond Collector (Silver)

예시

7 3

10 5 1 12 9 5 14

1. 먼저 sort 함.

=> a = [1 5 5 9 10 12 14]

2. i번째 다이아몬드를 시작으로 몇개까지 한 case 안에 들어갈수 있는지 갯수를 upper_bound를 이용하여 셈.

=> b = [1 2 1 3 2 2 1]

3. i번째 다이아몬드부터 최대한 한 case에 넣어봤을때, 뒤에 남은 다이아몬드들 중에서 최대로 넣을수 있는 갯수를 저장해둠.

=> c = [3 3 3 3 2 2 1]

4. 만일 0번째 다이아몬드(a[0])를 한 case에 넣으면 그 case에는 총 b[0] = 1개의 다이아몬드가 들어갈수 있음. 이때 다른 case에 들어갈수 있는 최대 다이아몬드의 갯수는 c[0 + b[0]] = c[1] = 3개이고, 이때 답은 4임. 만일 1번째 다이아몬드(a[1])을 한 case에 넣으면 그 case에는 총 b[1] = 2개의 다이아몬드가 들어갈수 있음. 이때 다른 case에 들어갈수 있는 최대 다이아몬드의 갯수는 c[1 + b[1]] = c[3] = 3개이고, 이때 답은 5임. 이런식으로 끝까지 훑으면서 답들중에 최대값을 구하면 됨.

#include <bits/stdc++.h>
using namespace std;
 
int n, k, a[50001], b[50001], c[50001];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
 
    for(int i = 0; i < n; i++)
        b[i] = upper_bound(a, a + n, a[i] + k) - a - i;
    for(int i = n - 1; i >= 0; i--)
        c[i] = max(b[i], c[i + 1]);
 
    int ans = 0;
    for(int i = 0; i < n; i++)
        ans = max(ans, b[i] + c[i + b[i]]);
 
    cout << ans << '\n';
    return 0;
 
}