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

https://www.acmicpc.net/problem/1337

1337번: 올바른 배열

---

문제풀이

접근 방법이 생각처럼 잘 떠오르지 않았다. 일단 연속되는 수를 찾아야 하기 때문에 정렬을 해 주어야겠다고 생각했다.

정렬한 값을 순서대로 보면서 어떻게 하면 추가해야 할 원소를 구할수 있지 않을까? 라고 고민해보았다.

그 결과 이런 방법이 떠올랐다.

정렬한 배열을 순회한다, 각 순회마다 배열 인덱스 1~4를 더한 곳의 배열 값을 가져와 현재 순회하는 배열의 값과 비교를 해서 만약 이 값이 5보다 작다면 이 값은 연속적인 5개 값 안에 들어간다는 뜻이 된다. 이렇게 1~4부터 반복해서 만약 4개가 모두 5보다 작다면, 해당 값은 연속적인 값이기 때문에 정답은 0이된다. 4개라면 하나만 더 넣으면 되므로 1이되고 이런식으로 구한 값에 5를 빼주면 된다.

예시를 보자.

 

1, 2, 3, 4, 5 라는 배열이있다.

현재 반복문은 1을 갖고 있다. cnt는 자기 자신은 무조건 연속적인 수에 포함 된다고 가정하므로 1부터 시작한다.

1과 2를 비교한다. 2-1은 5보다 작으므로 cnt를 1 증가시킨다.

1과 3을 비교한다. 3-1은 5보다 작으므로 cnt를 1 증가시킨다.

..

5까지 비교하고 나면 cnt는 5가된다.

즉 2, 3, 4, 5 는 모두 5보다 작게 차이가 난다는 뜻으로 연속적인 값임을 알 수 있다.

 

 

1, 3, 4, 5, 6 라는 배열이 있다.

5까지는 위와 마찬가지로 가지만, 6일 경우 6-1 은 5이므로 cnt가 증가되지 않는다.

결과적으로 cnt는 4가된다. 이 말은 연속적인 숫자가 4개 있다는 뜻이다. 즉 5에서 4를 빼주면 추가해야 될 숫자가 1개라는 것을 알 수있다.

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    int arr[50];
    for(int i=0; i<n; i++) cin >> arr[i];
    sort(arr, arr+n);

    int answer = 1;
    for(int i=0; i<n; i++) {
        int cnt = 1;
        for(int j=1; j<5; j++) {
            if(i+j < n && arr[i+j]-arr[i]<5) {
                cnt++;
            }
        }
        if(cnt >= 5) {
            cout << 0;
            return 0;
        }
        answer = max(answer, cnt);
    }

    cout << 5 - answer;
    return 0;
}