Codeforce Round #674 (Div.3) Virtual Participation 리뷰

A . Floor Number

---

방 번호가 주어지고, 해당 방이 몇 층에 있는지 구하는 문제이다. 보이는대로 풀면 된다. 다만 1층에 2개의 방이 있다고 (n-2)/x 를 하면 안 된다. x 가 5이고 2층에 3번 ~ 7번 방이 존재한다면 (7-2)/5 = 1 이기 때문이다.

 

#include <iostream>
 
using namespace std;
 
int main(void)
{
	int t, n, x;
	
	cin>>t;
	
	while(t--)
	{
		cin>>n>>x;
		
		if(n<3)
			cout<<"1\n";
		
		else
		{
			n = (n-3)/x+2;
			
			cout<<n<<'\n';
		}
	}
}

 

 

B. Symmetric Matrix

---

주어진 2x2 타일로, mxm 크기의 대칭 행렬을 만들 수 있는지 확인하는 문제이다. 하나의 타일을 중복해서 사용할 수 있엇서 입력되는 타일의 (1,2) 와 (2,1)이 같은지 확인하고 같다면 YES 를 출력하도록 구현했다.

 

처음에는 아래와 같이 (1,2) 와 (2,1) 이 다르더라도 짝이 맞는 타일이 있으면 가능할 것 같아 경우를 확인했다. 하지만 회색 부분과 같이 어떻게 하던 (1,2) 와 (2,1) 이 같은 타일이 하나는 있어야 한다는 걸 확인할 수 있었다.

 

8	9	5	2
9	8	1	4
5	1	8	9
2	4	9	8

 

#include <iostream>
 
using namespace std;
 
int main(void)
{
	int t, n, m;
	
	cin>>t;
	
	while(t--)
	{
		int v11,v12,v21,v22;
		bool flag = false;
		
		cin>>n>>m;
		
		for(int i=0; i<n; ++i)
		{
			cin>>v11>>v12>>v21>>v22;
			
			if(v12 == v21)
				flag = true;
		}
		
		if(m%2)
			flag = false;
		
		if(flag)
			cout<<"YES\n";
		
		else
			cout<<"NO\n";
	}
}

 

 

C. Increase and Copy

---

초기값이 [1] 인 수열이 있고, 수열의 한 원소를 복사하거나, 수열의 한 원소 값을 1 증가하는 행동을 취할 수 있다. 이때 수열의 합이 n 이 되도록하는 최소 행동 횟수를 구하는 문제이다.

 

적절한 값 Key value 까지 증가시킨 뒤 iter 횟수만큼 복사해서 행동 횟수 = (Key value - 1) + (iter - 1) 가 최소가 되도록 구현했다. 적절한 값을 구해야하는 걸 보니 손익분기점이 생각나서 y축에 iter 횟수, x축에 Key value 값을 넣고 그래프를 그려봤다. 확인해보니 특정 값 이후부터는 행동 횟수가 무조건 늘어나서 행동 횟수가 늘어나면 갱신하지 않고 종료하도록 구현했다.

 

시간 초과날 것 같아서 딱히 기대하지 않고, 제출했는데 Accepted 받았다. 1,000,000,000 를 입력했을 때 O(1,000,000,000) 이 아니라 O(key) 여서 시간 안에 풀 수 있는 것 같다.

 

#include <iostream>
 
using namespace std;
 
int n, res;
 
void checkCount(int key)
{
	int tmp = key - 1 + n/key - 1;
	
	if(n%key)
		++tmp;
	
	if(res < tmp)
		return;
	
	res = tmp;
	
	if(key == n)
		return;
	
	checkCount(key+1);
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
	int t;
	
	cin>>t;
	
	while(t--)
	{
		res=1000000001;
		
		cin>>n;
		
		checkCount(1);
		
		cout<<res<<'\n';
	}
}

 

 

D. Non-zero Segments

---

0이 포함되지 않은 집합을 입력 받고, 이 집합에서 합이 0인 부분 집합이 있다면 아무 위치에 특정 원소를 끼워넣어 합이 0이 되지 않도록 만들 수 있다. 이 때 몇 개를 끼워넣어야 부분 집합의 합이 0이 되지 않는지 찾는 문제이다.

 

처음에는 index 0 부터 탐색해서 합이 0이 되면 ans 를 1 증가시키는 방식으로 구현했다. 하지만 '합이 0이 되는 부분 집합' 안에 '합이 0이 되는 부분 집합'이 있으면 1번 증가시켜도 되는걸 중복으로 증가시켜서 이것 저것 시도하다가 결국 재귀로 풀었다. 제출하고 나니 test 10 에서 틀렸다고 나와서 TC 만들고 수정하니 이번에는 test 11 에서 틀렸다고 나왔다. 여기까지 1시간 30분동안 풀고, 풀이를 보기로 했다.

 

구글링 하다가 sKSama 라는 분의 코드를 봤는데 아래 2가지 개념으로 쉽게 풀이한 걸 확인할 수 있었다.

 

1. 특정 위치에 값을 끼워넣으면, 이전 값들은 무시해도 된다.

2. 꼭 0이 되도록 고집하지 않고, 원래의 값으로 돌아오는 부분을 확인하는 방법으로 풀 수 있다.

 

위 2가지 개념으로 순차적으로 입력받으며 바로 풀이할 수 있었다.

 

#include <iostream>
#include <set>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, input;
	long long tot=0 ,cnt=0;
	
	set<long long> sum;
	
	cin>>n;
	
	sum.insert(0);
	
	for(int i=0; i<n; ++i)
	{
		cin>>input;
		
		tot += input;
		
		if(sum.find(tot) != sum.end())
		{
			sum.clear();
			sum.insert(0);
			tot = input;
			sum.insert(tot);
			++cnt;
		}
		
		else
			sum.insert(tot);
	}
	
	cout<<cnt<<'\n';
}

 

풀이 코드 링크 : codeforces.com/contest/1426/submission/94127577

Submission #94127577 - Codeforces

 

 

E. Rock, Paper, Scissors

---

가위바위보 판 수와 각각 뭘 몇 번씩 낼 지 주어질 때, 최대 승수와 최소 승수를 구하는 문제이다. 최대 승수를 구하는 건 간단했고, 최소 승수를 구하는 건 어려워보이면서도 쉬웠다. 

 

최소 승수를 구하기 위해서는 Alice 가 지거나 비겨야 했는데, 글만 보고서는 어떻게 할 지 모르겠어서 그림으로 그려봤다.

 

위가 Alice 의 경우이고, 아래가 Bob 의 경우이다. R->P 로 R 을 없앨 수 있는대로 없애고, R 이 남으면 R->R 을 확인해서 없앤다. 이대로 P 까지 진행하고 Alice 의 RSP 에 남은 값이 Alice 의 최종 승수이다. 구성한 논리에 테스트케이스 몇 개 만들어서 넣어보던 중 한 가지 모순되는 경우가 있었다. Alice 1 0 29, Bob 29 0 1 인 경우, minimum 은 28이 되어야 하는데 내 논리대로라면 29가 나오는 경우이다. 확인해보니 지는 경우를 비기는 경우보다 먼저 적용해서 생기는 문제였고, 비기는 경우를 지는 경우보다 먼저 적용한 것과 비교해서 더 작은 것을 minimum 으로 넣었다.

 

처음 구현할 때는 이 과정을 while(tmpB[B] && tmpA[A]) 로 진행했는데, 시간 초과가 나왔다. 지금 생각해보면 당연한 건데 깔끔하게 구현하는 것에 초점이 맞춰져서 이렇게 구현했다. 이는 min 변수에 빼야할 값을 할당한 뒤 계산하는 방법으로 해결했다.

 

#include <iostream>
#include <vector>

using namespace std;

int minFront, minBack, max, value;
vector<int> tmpA, tmpB;

void calc(int A, int B)
{
	int min = (tmpA[A] > tmpB[B])?tmpB[B]:tmpA[A];
	
	tmpB[B] -= min;
	tmpA[A] -= min;
	value -= min;
}


int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, min, max;
	vector<int> a(3,0);
	vector<int> b(3,0);
	
	cin>>n;
	
	for(int i=0; i<3; ++i)
		cin>>a[i];
	
	for(int i=0; i<3; ++i)
		cin>>b[i];
	
	tmpA = a;
	tmpB = b;
	value = n;
	
	calc(0,2);
	calc(0,0);
	calc(1,0);
	calc(1,1);
	calc(2,1);
	calc(2,2);
	
	minFront = value;
	
	tmpA = a;
	tmpB = b;
	value = n;
	
	calc(2,2);
	calc(2,1);
	calc(1,1);
	calc(1,0);
	calc(0,0);
	calc(0,2);
	
	minBack = value;
	
	tmpA = a;
	tmpB = b;
	value = n;
	
	calc(0,1);
	calc(1,2);
	calc(2,0);
	
	if(minFront>minBack)
		minFront = minBack;
	
	cout<<minFront<<' '<<n-value<<'\n';
}

 

 

알아가야할 것들

---

1. 코드가 생각대로 동작하지 않을 경우, 인덱스를 확인하자. ( 1 차이 ) -> 용어 수정

2. 반복문 최소화

 

후기

---

슬럼프가 한달 가까이 지속되고, 알고리즘을 손에 대지 않아서 뭐라도 해야된다는 생각에 예전에 세웠던 계획대로 Codeforce 에 참여했다. 솔직히 알고리즘에 재미를 못 느끼고 있어서, virtual participation 으로 참여 신청하고, 3분의 대기시간동안 웹툰보다가 슬렁 슬렁 시작했다.

 

백준과는 다르게 영어로 되어있어서 이해하는데 시간이 걸렸고, 구현 능력에 문제가 있어서  A, B 에 20분씩 시간을 썼다. A 번의 경우, 제출을 g++ 가 아닌 gcc 로 해서 생긴 오류를 확인하느라 시간이 조금 더 걸렸다.

 

C 번은 생각을 안 하고 풀다가, 문제의 감을 잡은 뒤 하나 하나 생각하고 시도해보며 풀었다. 제출하려고 보니까 시간이 5초 남아서 Round 가 끝난 뒤에 제출하고 Accepted 를 받았다. 1시간 30분 정도 걸린 것 같다. 아쉬웠고, 즐거웠다. 쉬운 문제라고 하더라도, 최근에 알고리즘에 실증을 느껴 문제를 봐도 생각이 안 나 접근을 못 했는데, 오랜만에 재밌게 풀었다. 

 

순차적으로 푸니 D, E, H 는 보지도 못하고 끝났다. 다음에 참여할 때는 A, B 빠르게 풀고 흝어본 뒤 나머지 풀도록 하자.

 

D 번 부터는 Round 끝나고, 개인적으로 풀었다.

처음에 떠오른 개념을 가능한 지 고민해보고 구조화하는 게 중요하다.

 

6558등