[SWEA] 9088 다이아몬드

[SWEA] 9088 다이아몬드 - c

문제

문제를 잘 읽는 것의 중요성

문제를 잘 읽으면 쉽다. 하지만 문제 잘 읽기가 어렵다.

묶음이 여러 묶음일 수 있다는 말이 함정

• 크기가 k이하로 차이나는 묶음이 여러개 모인다면 결국 크기 차이가 k 이상인 것. == 다이아몬드의 크기가 뒤죽박죽인 것.
• 다이아몬드의 크기가 뒤죽박죽이면 애인이 좋아하지 않는다. == 선물하지 않는다.
• 따라서 묶음 하나만 선물한다.

결국 문제는 묶음 하나에 최대로 몇개의 다이아몬드가 들어갈것이냐?를 묻는 것이다.

해결 방법

1. 다이아몬드의 크기가 섞여서 들어오기 때문에 받은 후 정렬을 해야한다. == 퀵정렬 사용
2. 앞에서부터 순서대로 그 다음 위치에 있는 다이아몬드와 크기를 비교한다.
3. 현재 위치에서부터 마지막까지 남은 다이아의 수 보다 현재 최대 묶음의 수가 크면 종료한다.

4. C언어

   • 메모리 8,604 kb
   • 실행시간 5 ms

   #include <stdio.h>
   int tc;
   int n, k;
   int size[1000] = { 0, };
   int start, sum;
   int result;
   
   void quick_sort(int *arr, int l, int r) {
   	int L = l, R = r;
   	if (L > R) return;
   
   	int mid = (L + R) / 2;
   	int pivot = arr[mid];
   	while (L <= R) {
   		while (arr[L] < pivot) L++;
   		while (pivot < arr[R]) R--;
   		
   		if (L <= R) {
   			int temp = arr[L];
   			arr[L] = arr[R];
   			arr[R] = temp;
   			L++;
   			R--;
   		}
   	}
   	if (L < r) quick_sort(arr, L, r);
   	if (l < R) quick_sort(arr, l, R);
   }
   
   
   int main(void) {
   	scanf("%d ", &tc);
   	for (int t = 1; t <= tc; t++) {
   		scanf("%d %d ", &n, &k);
         
         // 입력 후 정렬
   		for (int i = 0; i < n; i++) scanf("%d", &size[i]);
   		quick_sort(size, 0, n - 1);
   		
         // 최대 갯수 초기화
         result = 0;
   		for (int i = 0; i < n - 1; i++) {
             // 비교 할 첫번째 다이아 선택
   			start = size[i];
             // 갯수 초기화
   			sum = 1;
             // 현재 남은 갯수가 최대갯수보다 작으면 반복문 종료
   			if (n - i < result) break;
             // 비교는 start 다음부터 마지막까지
   			for (int j = i + 1; j < n; j++) {
   				if (size[j] - start <= k) sum++;
   				else break;
   			}
   			if (result < sum) result = sum;
   		}
   
   		printf("#%d %d\n", t, result);
   	
   	}
   	return 0;
   }