백준 BOJ 1337 - 올바른 배열

구현 문제.

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

1337번: 올바른 배열

 

O(5N) 등의 다양한 풀이가 있는듯 한데,

나는 O(N^2) 풀이를 구상했고 이걸로 구현해서 정답을 받았다.

 

일단 입력으로 주어진 배열을 정렬한 다음에,

두 인덱스 i와 j ( i < j ) 를 잡는다.

해당 인덱스에 있는 배열 값의 차는 v[i] - v[j] 이고,

해당 인덱스 구간에 있는 배열 값의 갯수는 i-j+1이다.

 

추가해야할 원소를 최소로 만들기 위해서

배열 값의 갯수가 최대가 되게 해야하므로

이 최대를 $ans$라 한다.

 

배열 값의 차가 4 이하여서 이 두 수를 전부 포함하는 올바른 배열을 만들 수 있는 경우,

$ans$를 배열 값의 갯수 $i-j+1$ 과 $ans$중 최댓값으로 갱신한다.

 

올바른 배열을 만들수 있는 경우인데 $i-j+1$이 2보다 큰 경우,

v[i]와 v[j]의 사이에 올바른 배열에 포함되는 또다른 수 v[k] ( $v[i] < v[k] < v[j]$ )가 있음을 알려주기 때문에,

해당 인덱스 구간 안에 있는 모든 수는 전부 올바른 배열 안에 포함되게 된다.

 

구해준 $ans$는 배열 값의 갯수이므로

올바른 배열의 크기 5에서 $ans$를 빼서 출력한다.

 

#include <bits/stdc++.h>
using namespace std;

vector<int> v;

int main(){
	int N,k;
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> k;
		v.push_back(k);
	}
	
	int ans = 1;
	
	sort(v.begin(), v.end());
	for(int i=0; i<N; i++){
		for(int j=i+1; j<N; j++){
			int val = v[j]-v[i];
			int cnt = j-i+1;
			
			if(val <= 4){
				ans = max(ans, cnt);
			}
		}
	}
	
	cout << 5-ans;
	return 0;
}