codeforces #604 div2 D - Beatiful Sequence (수학,발상)

http://codeforces.com/contest/1265/problem/D

- 댓글풀이

 

<문제설명>

0,1,2,3이 각각 a,b,c,d번 나오는 숫자의 배열 a 를 만드는데 다음 조건을 만족해야 한다.

 

<풀이> 

문제의 조건을 만족하기 위해선, 어떤 연속한 수도 같은 parity를 가질 수 없다. 따라서,

 

1. 배열의 크기가 홀수인 경우엔 cnt(even)와 cnt(odd)가 1 차이가 나야 한다.

cnt(even)이 더 큰 경우 0과 2를 배열a의 홀수번 idx에 순서대로 배치하고,  1과 3을 배열 a의 짝수 idx에 순서대로 배치하면 된다.

cnt(odd)가 더 큰 경우는 그 반대로 하면 된다.

 

2. 배열의 크기가 짝수일 경우엔 cnt(even)=cnt(odd)

1번처럼 하면 된다. 무엇을 먼저 배치할진 자유

 

그리고 만들어진 배열이 조건을 만족하는지 확인해 준 후 출력한다.

 

(확인하는 이유)

2 2 2 3 이 입력으로 들어오면 조건에 맞는 배열을 만들어 낼 수 없다.

 

 

<코드>

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 1e5 + 5;

int main() {
	int even = 0, odd = 0;
	int a, b, c, d; cin >> a >> b >> c >> d;
	even += a + c;
	odd += b + d;
	int ans[MAX];

	
	bool flag = false;

	if (even == odd + 1 || even == odd) {
		for (int i = 0; i < even; i++)
			ans[i * 2] = i < a ? 0 : 2;
		for (int i = 0; i < odd; i++)
			ans[i * 2 + 1] = i < b ? 1 : 3;
	}
	else if (even + 1 == odd) {
		for (int i = 0; i < odd; i++)
			ans[i * 2] = i < b ? 1 : 3;
		for (int i = 0; i < even; i++)
			ans[i * 2 + 1] = i < a ? 0 : 2;
	}
	else flag = true;

	for (int i = 0; i < odd + even - 1; i++)
		if (abs(ans[i + 1] - ans[i]) > 1) flag = true;

	if (flag) {
		cout << "NO\n";
	}
	else {
		cout << "YES\n";
		for (int i = 0; i < odd + even; i++)
			cout << ans[i] << " ";
		cout << '\n';
	}

}

 

 

<생각>

마지막에 조건에 맞는지 확인하는 과정이 있다는 점에서 완벽한 풀이가 아니라는 생각이 든다.