[codeforces] 1150C. Prefix Sum Primes

문제

https://codeforces.com/contest/1150/problem/C

Problem - C - Codeforces

 

풀이

2를 제외한 모든 소수는 홀수이다.

따라서, 주어진 순열을 2 1 2 2 2 ... 2 2 1 ... 1 1 1의 형태로 놓는다면, $\sum a_i$이하의 모든 소수를 포함하게 된다.

이것이 불가능한 경우는, 모두 1이거나 모두 2인 경우뿐이므로, 이 경우만 따로 출력한다.

 

Time Complexity : $O(n)$

 

코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
	int n, onenum=0, twonum=0;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int x;
		scanf("%d",&x);
		if(x==1) onenum++;
		else twonum++;
	}

	if(onenum==0)
	{
		for(int i=0;i<n;i++) cout<<"2 ";
	}
	else if(twonum==0)
	{
		for(int i=0;i<n;i++) cout<<"1 ";
	}
	else
	{
		cout<<"2 1 ";
		for(int i=0;i<twonum-1;i++) cout<<"2 ";
		for(int i=0;i<onenum-1;i++) cout<<"1 ";
	}
}