[ SWEA 9088 ] 다이아몬드 (C++)

SWExpertAcademy의 다이아몬드(9088 / D4) 문제이다.

[ 문제풀이 ]

고른 다이아몬드의 크기가 모두 K이하인 것들을 묶을 때, 최대 몇 개의 다이아몬드를 선물할 수 있는지 구해야 하는 문제이다.

본인은 가장 먼저 다이아몬드의 크기를 오름차순으로 정렬해 주었다.

그 이후, 반복문을 통해서 모든 경우의 수를 계산해 주었다.

기준 값이 되는 하나의 다이아몬드 크기를 설정한 후, 모든 다이아몬드의 크기를 비교해보면서 K 이하로 묶여질 수 있는

다이아몬드 갯수를 Count해서 최댓값을 저장해 주었다.

다이아몬드 크기가 오름차순으로 정렬되어 있기 때문에, 다이아몬드의 크기를 비교했을 때 K 이하로 묶여질 수 없는 다이아몬드

가 나오게 된다면 탐색을 하는 반복문을 그대로 종료해주면 된다.

왜냐하면 그 이후에 나오는 다이아몬드들을 당연히 기준이 되는 다이아몬드와 크기를 비교했을 때 K 보다 더 클 것이기 때문이다.

[ 소스코드 ]

#include<iostream>
#include<algorithm>
#include<cstring>
 
#define endl "\n"
#define MAX 1000
using namespace std;
 
int N, K, Answer;
int Arr[MAX];
bool Visit[MAX];
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Initialize()
{
    Answer = 0;
    memset(Visit, false, sizeof(Visit));
}
 
void Input()
{
    cin >> N >> K;
    for (int i = 0; i < N; i++) cin >> Arr[i];
}
 
void Solution()
{
    sort(Arr, Arr + N);
    for (int i = 0; i < N; i++)
    {
        int Result = 1;
        for (int j = i + 1; j < N; j++)
        {
            if (Arr[j] - Arr[i] <= K) Result++;
            else break;
        }
 
        Answer = Bigger(Answer, Result);
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}