문제

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

 

Problem - C - Codeforces

 

codeforces.com

 

풀이

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 ";
	}
}

 

'PS > codeforces' 카테고리의 다른 글

[codeforces] 1150E. Tree Generator™  (0) 2019.05.01
[codeforces] 1150D. Three Religions  (0) 2019.04.30
[codeforces] 1150B. Tiling Challenge  (0) 2019.04.30
[codeforces] 1150A. Stock Arbitraging  (0) 2019.04.30

문제

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

 

Problem - B - Codeforces

 

codeforces.com

 

풀이

왼쪽 위부터 순서대로 채운다. 이렇게 채워도 가능한 모든 경우를 다 볼수 있다는 것이 증명 가능하다.

 

# # # # #
# ㅇ      
ㅇ ㅇ ㅇ    
  ㅇ      

저 첫 빈칸을 채우기 위해서는 저 첫 빈칸을 위쪽타일로 하는 십자타일을 놓는 경우 외에는 존재하지 않는다.

따라서, 이 타일을 전부 채울수 있는 경우가 있다면, 저 곳은 o로 포함된 타일 모양으로 채워야 하고, 이를 반복적으로 진행하여, 다 채울 수 있는지 확인한다.

 

Time Complexity : $O(n^2)$

 

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define N 52
using namespace std;

int n;
string mp[N];
bool f(int p,int q)
{
	if(p<0 || q<0 || p>=n || q>=n) return false;
	return mp[p][q]=='.';
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++) cin>>mp[i];

	for(int i=0;i<n*n;i++)
	{
		if(mp[i/n][i%n]=='#')continue;
		int x=i/n, y=i%n;
		if( !f(x,y) || !f(x+1, y-1) || !f(x+1, y) || !f(x+1, y+1) || !f(x+2, y))
		{
			cout<<"NO";
			return 0;
		}
		mp[x][y]=mp[x+1][y-1]=mp[x+1][y]=mp[x+1][y+1]=mp[x+2][y]='#';
	}
	cout<<"YES";
}

'PS > codeforces' 카테고리의 다른 글

[codeforces] 1150E. Tree Generator™  (0) 2019.05.01
[codeforces] 1150D. Three Religions  (0) 2019.04.30
[codeforces] 1150C. Prefix Sum Primes  (0) 2019.04.30
[codeforces] 1150A. Stock Arbitraging  (0) 2019.04.30

문제

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

 

Problem - A - Codeforces

 

codeforces.com

 

풀이

가장 저렴하게 구매해서, 가장 비싸게 파는 것이 유리하다.

$smin=\min(s_i)$와 $bmax=\max(b_i)$를 구하자.

가능한 만큼, $smin$원에 구매하고, $smax$원에 판매하면 된다.

 

Time Complexity : $O(n+m)$

 

코드

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

using namespace std;
int main()
{
	int n,m,r,x;
	int smin=10000,bmax=0;

	cin>>n>>m>>r;
	for(int i=0;i<n;i++)
	{
		cin>>x;
		if(smin>x)smin=x;
	}
	for(int i=0;i<m;i++)
	{
		cin>>x;
		if(bmax<x)bmax=x;
	}

	if(smin>=bmax) cout<<r;
	else cout<<(r/smin)*bmax+r%smin;
}

 

'PS > codeforces' 카테고리의 다른 글

[codeforces] 1150E. Tree Generator™  (0) 2019.05.01
[codeforces] 1150D. Three Religions  (0) 2019.04.30
[codeforces] 1150C. Prefix Sum Primes  (0) 2019.04.30
[codeforces] 1150B. Tiling Challenge  (0) 2019.04.30

+ Recent posts

티스토리툴바