[백준 1337번] 올바른 배열 (C++)

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N, arr[51];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;

    for(int i=0; i<N; i++) cin >> arr[i];

    sort(arr, arr+N);

    int cnt = 1;

    for(int i=0; i<N; i++)
    {   
        for(int j=i+1; j<N; j++)
        {
            if(arr[j]-arr[i] <=4) //현재값 기준 4칸까지 가능
            {
                cnt = max(cnt , j-i+1); //범위내 최대 길이 저장
            }
        }
    }

    cout << 5-cnt; //부족한 값 출력
    return 0;
}

 

먼저 입력받은 배열에 대해 정렬해주고 시작한다.

올바른 배열의 길이가 5이므로, 현재 값을 기준으로 최대 +4의 값까지 길이 확장이 가능하다.

따라서 현재 위치의 값과 앞에 있는 값들의 차이를 확인하고, 해당 차이가 4보다 같거나 작다면 같은 배열로 두는 것이 가능하다는 것이다.

 

가능한 범위 기준으로 최대 길이 값을 따로 저장하고, 올바른 배열의 길이인 5에서 최대 길이 값을 빼면 올바른 배열에서 부족한 최소값을 얻을 수 있다.