백준 12005 Diamond Collector (USACO US Open 2016 Bronze 1번)

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

12005번: Diamond Collector (Bronze)

각각의 diamond를 제일 작은 size라고 취급하고, 같은 case 안에 들어갈수 있는 diamond 갯수를 세서, 최대값을 구함.

시간복잡도 O(N^2).

#include <bits/stdc++.h>
using namespace std;
 
int N, K, d[10001];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N >> K;
    for(int i = 0; i < N; i++) cin >> d[i];
 
    int ans = 0;
    for(int i = 0; i < N; i++) {
        int cnt = 0;
        for(int j = 0; j < N; j++) {
            if(d[j] >= d[i] && d[j] - d[i] <= K)
                cnt++;
        }
        ans = max(ans, cnt);
    }
 
    cout << ans << '\n';
    return 0;
}