9088. 다이아몬드 D4

오늘도 D4 한 문제....

일단 문제부터 보자

태영이는 N개의 다이아몬드를 가지고 있다. 각 다이아몬드 크기는 1 이상 10000 이하의 자연수로 나타낼 수 있다.

태영이는 N개의 다이아몬드 중 몇 개를 골라, 애인에게 선물로 주려고 한다. 

한편, 태영이는 고른 다이아몬드의 크기가 뒤죽박죽이면 애인이 좋아하지 않을 것이라고 생각하여,

고른 다이아몬드 중 크기 차가 K 이하인 것들을 묶음으로 가져가려고 한다. (단, 묶음은 여러 묶음일 수 있다.)

태영이가 애인에게 선물할 수 있는 다이아몬드의 최대 개수는 얼마인가 

[입력] 

첫 번째 줄에 테스트 케이스의 수 TC 가 주어진다.
이후 TC 개의 테스트 케이스가 새 줄로 구분되어 주어진다. 각 테스트 케이스는 다음과 같이 구성되었다.

첫 번째 줄에 자연수 N, K가 주어진다. (1 ≤ N ≤ 1000, 0≤ K ≤ 10000)
이후 N개의 줄에 다이아몬드의 크기가 주어진다.


[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

태영이가 선물할 수 있는 다이아몬드의 최대 개수를 출력하라.

문제는 이렇다.

태영이는 여러 개의 다이아몬드가 있는데 그 중에 차이가 K 이하인 것들을 묶어서 묶음 안에 들어가는 다이아몬드의 개수가 가장 큰 개수를 출력하는 문제다.

먼저 접근한 방식은

1. 입력을 받고 오름차순으로 sort

2. for문을 돌려 차이가 K 이하인 것들을 찾을때 temp++

3. temp가 원래 ret값보다 크다면 ret=temp

4. 자기 자신도 개수에 포함해야 하므로 temp=1에서 시작

작성 코드

#include <iostream>
#include <algorithm>
using namespace std;
int solve(int *ARR, int K,int SIZE)
{
    int temp,ret = 0;
    for(int i=0;i<SIZE;i++)
    {
        temp=1;
        for(int j=1;i+j<SIZE&&ARR[i+j]-ARR[i]<=K;j++)
        {
            //cout<<ARR[i+j]-ARR[i]<<' ';
            temp++;
        }
        if(temp>ret)
            ret=temp;
    }
    return ret;
}
int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    int TC,N,K;
    cin>>TC;
    for (int t=1;t<=TC;t++)
    {
        cin>>N>>K;
        int *ARR = new int[N];
        for(int i=0;i<N;i++)
            cin>>ARR[i];
        sort(ARR, ARR+N);
        cout<<"#"<<t<<' '<<solve(ARR,K,N)<<'\n';
    }
    return 0;
}
 

차이를 확인하려고 만든 각주 줄을 빼는 것을 까먹어서 괜히 한 번 틀렸다 ㅎㅎ;;