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

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

1337번: 올바른 배열

 

어떤 배열 속에 있는 원소 중 5개가 연속적일 때 올바른 배열이라 한다. 배열이 주어졌을 때 올바른 배열이 되기 위해 추가되어야 할 원소의 최소 개수를 구하는 문제이다.

 

이중 반복문을 사용해 풀어주었다.

1. 배열을 정렬

2. 배열의 비교 원소가 해당 원소의 올바른 배열에 포함되는지 확인 -> 차이값이 5미만이면 된다.

1,2를 모든 원소에 반복하면 배열에서 가장 긴 연속되는 원소의 길이를 구할 수 있다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int a[51];

int main(void) {
	int N;
	cin >> N;
	
	for(int i=0; i<N; i++) {
		cin >> a[i];
	}
	
	sort(a, a+N);
	
	int max=0;
	for(int i=0; i<N; i++) {
		int l=1;
		for(int j=i+1; j<N; j++) {
			if(a[j]-a[i]<5 && a[j]-a[i]>0) l++;
		}
		if(l>max) max=l;
	}
	
	cout << 5-max;
}