[SWEA] 9088 다이아몬드

출처: SWEA

 Input 

2

2 0

1

1

3 3

1

6

4

 

 Output 

#1 2

#2 2

 

"선택된 다이아몬드 크기 차이가 K 이하인 것들"을 처리할 때는

선택된 다이아 중 가장 작은 크기와 가장 큰 크기의 차이가 K 이하인 경우를 의미합니다.

계수 정렬과 같이 diamond[]에 다이아몬드 크기별 개수를 저장합니다.

 

left를 기준으로 k 간격만큼 떨어진 지점을 right로 두어서

left와 right 사이의 다이아몬드 개수를 셉니다. 그 중 가장 많이 선택될 수 있는 경우를 출력

---

#include <iostream>
#include <cstring>
using namespace std;
#define MAX 10000
 
int n, k;
int diamond[MAX + 1]; // 0~10000 크기의 다이아몬드
int answer;
int main() {
    int testCase; cin >> testCase;
 
    for (int tc = 1; tc <= testCase; tc++) {
        cin >> n >> k;
        answer = 0;
        memset(diamond, 0, sizeof(diamond));
 
        
 
        int idx;
        for (int i = 0; i < n; i++) {
            // 크기별 다이아몬드 개수 입력 받기
            cin >> idx; diamond[idx]++;
        }
 
        int right, cnt;
        for (int left = 0; left <= MAX - k; left++) {
            right = left + k;
            // pivot 기준 크기가 K이하인 다이아몬드 개수 세기
            cnt = 0;
            for (int i = left; i <= right; i++) {
                cnt += diamond[i];
            }
            answer = answer < cnt ? cnt : answer;
        }
 
        printf("#%d %d\n", tc, answer);
    }
}