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

 

으... 너무 졸리다...

아직 시차적응이 안된건가...??

(아니면 그냥 피곤한걸수도)

 

얼른 끝내버리자~~~

 

 

문제 1337번

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

1337번: 올바른 배열

 

처음에 문제를 읽고 그냥 없는 숫자를 추가하면 되는거 아닌가 하다가 이해를 잘못해서 이상하게 코드를 작성하였다.

그래서 다른 분의 풀이를 참고했다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	vector<int> num;
	int n,k;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> k;
		num.push_back(k);
	}

	sort(num.begin(), num.end());
	int res = 1;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			int val = num[j] - num[i];
			int count = j - i + 1;
			
			if (val <= 4) {
				res = max(res, count);
			}
		}
	}

	cout << 5 - res << '\n';
	
}

 

 

일단 입력을 받은 후에 해당 값들을 오름차순으로 정렬해준다. 

추가해야할 원소를 최소로 만들기 위해서 배열 값의 갯수가 최대가 되게 해야한다고 해서 그 최대를 res로 잡았다.

해당 인덱스에 있는 배열 값의 차를 val에 넣고, 해당 인덱스 구간에 있는 배열 값의 갯수는 count에 넣었다.

배열 값의 차가 4이하여서 해당 두 수를 전부 포함하는 올바른 배열을 만들 수 있다면 res를 res와 count 중 더 큰 값으로 갱신한다. 구해준 res는 배열 값의 갯수이기 때문에 올바른 배열의 크기인 5에서 res를 빼주면 원하는 값을 출력할 수 있다.

[참고] https://koder0205.tistory.com/350

 

 

 

 

 

처음에는 무슨 소리인지 몰라서 계속 이해하려고 노력했다. 드디어 이해할 수 있었지만, 다음에 보면 또 잊어버릴 것 같아서 복습이 필요할 것 같다.