Codeforces Round #693 (Div. 3)

문제 링크

codeforces.com/contest/1472

 

A. Cards for Friends

문제

n명의 친구들에게 w x h 크기의 종이를 잘라 나누어 주고자 한다.

자르는 데에는 두 가지 규칙이 있다.

 

• w가 짝수일 때, 종이는 반으로 잘라 (w/2) x h 크기 종이 2장으로 만들 수 있다.
• h가 짝수일 때, 종이는 반으로 잘라 w x (h / 2) 크기 종이 2장으로 만들 수 있다. 

 

주어진 w x h 크기 종이를 적당히 잘라 최소 n 조각을 만들 수 있는가?

 

풀이1

w, h 는 반드시 "짝수" 여야 종이의 개수를 늘릴 수 있다.

여기서 종이는 정확히 x 조각을 맞출 필요가 없기 때문에, 최대한 늘이는 방향으로 생각하자.

따라서, 종이의 최대 개수는 w, h 를 각각 "더 이상 짝수가 아닐 때까지" 2로 나누면서 전체 종이의 개수를 x2 해준다. ex. w = 8, h = 4 라면, 8 = 2^3 , 4 = 2^2 이므로 2^5 = 32개의 조각이 나온다.

따라서 자를 수 있는 만큼 모두 자른 종이의 개수와 입력으로 들어온 n을 비교하여 출력하면 된다.

소스 코드1

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--)
	{
		int w, h, n;
		cin >> w >> h >> n;
		int sum = 1;
		while (w % 2 == 0) {
			sum *= 2;
			w /= 2;
		}
		while (h % 2 == 0) {
			sum *= 2;
			h /= 2;
		}
		if (sum >= n) cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}

풀이2

 풀이 1과 모양만 다르고 원리는 같습니다. 

함수를 새로 만들어 최대치를 반환하도록 하였고, 최대치가 n이상이면 YES를 출력했습니다.

소스 코드2

#include <iostream>
using namespace std;

int into_pieces(int w, int h)
{
	int cnt = 1;

	while(w%2==0)
	{
		cnt *= 2;
		w /= 2;
	}
	while(h%2==0)
	{
		cnt *= 2;
		h /= 2;
	}
	return cnt;
}

int main()
{
	int t, w, h, n, cnt;
	cin >> t;

	while (t--)
	{
		cin >> w >> h >> n;
		cnt = into_pieces(w, h);
		if (n<=cnt) cout << "YES\n";
		else cout << "NO\n";
	}
}

B. Fair Division

 

문제

Alice와 Bob은 무게가 1 또는 2 그램인 n개의 양초를 나눠가지려 한다. 정확히 나누어 가질 수 있겠는가?

 

풀이1

우선 이 문제에서는 절대 안 되는 두 가지 상황을 배제하면 답이 나온다.

첫 번째, "1"의 개수가 홀수인 경우, 어떻게 조합을 해도 총 그램수가 홀수이므로 불가능하다.

두 번째, "2"의 개수가 홀수이고, "1"의 개수가 2보다 작은 경우 2g의 양초는 Alice와 Bob에게 동등하게 분배되지 않기 때문에 1g인 양초가 최소 2개는 있어야 한다. 따라서 불가능하다.

위 두 경우를 배제한 모든 경우는 양초를 동등하게 나눠가질 수 있다.

소스 코드1

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--)
	{
		int n; cin >> n;
		int one = 0, two = 0;
		for (int i = 0; i < n; i++)
		{
			int tmp; cin >> tmp;
			if (tmp == 1) one++;
			else two++;
		}
		if (one % 2 == 1) cout << "NO\n";
		else {
			if (two % 2 == 0) cout << "YES\n";
			else {
				if (one >= 2) cout << "YES\n";
				else cout << "NO\n";
			}
		}
	}
	return 0;
}

 

 

C. Long Jumps

 

문제

n개의 정수로 이루어진 배열을 가지고 몇 가지 규칙에 의해 놀이를 할 것이다.

첫 번째, 1 ~ n 사이의 정수 i를 고른 후, 시작 지점으로 둔다.

두 번째, i가 n보다 작거나 같을 때까지, ai를 점수에 추가한 후, i = i + ai 연산을 취한다.

만약 i가 n보다 크면 이 게임을 그만둔다.

얻을 수 있는 최대 점수는 몇 점인가?

 

풀이1

다이내믹 프로그래밍 문제이다.

dp[i] : i번까지 왔을 때, 얻을 수 있는 최대 점수라고 하면

dp[i + ai] = max(dp[i + ai] , dp[i] + ai) 가 성립된다.

 

여기서 중요하게 볼 점은, 문제에서 주어지는 모든 ai는 양수이므로, 반대로 돌아가지 않는다는 점이다. 따라서 부분 문제 조건이 성립되고 위 방식처럼 dp로 해결 가능하고, 시간 복잡도는 O(n)이다.

소스 코드1

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
ll dp[200010];
 
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--){
		memset(dp, 0, sizeof(dp));
		int n; cin >> n;
		vector<ll>v(n);
		for (int i = 0; i < n; i++) {
			cin >> v[i];
		}
		ll ans = 0;
		for (int i = 0; i < n; i++)
		{
			ll tmp = i + v[i];
			if (tmp > n - 1) ans = max(ans, dp[i] + v[i]);
			else {
				dp[tmp] = max(dp[tmp], dp[i] + v[i]);
			}
		}
		for (int i = 0; i < n; i++) {
			ans = max(ans, dp[i]);
		}
		cout << ans << "\n";
	}
	return 0;
}

 

D. Even-Odd Game

 

문제

Alice와 Bob은 n개의 정수를 담고 있는 배열을 사용해 다음과 같은 게임을 하고자 한다.

Alice가 먼저 시작하며, Alice가 짝수를 선택하면, 그 수는 Alice의 점수에 추가된다. 하지만, 홀수를 선택하면 점수에 변화가 없다.

이와 비슷하게 Bob은 홀수를 선택해야 점수가 되고, 짝수는 점수에 영향을 주지 않는다.

 

이와 같은 게임을 서로가 이기기 위해 최선을 다해 진행하였을 때, 누가 이길 것인가?

 

풀이1

일반적인 게임 문제이다.

보통 서로 턴을 주고받는 게임 문제에서는 어떤 사람이 선택을 했을 때, 그 선택에 따른 이익을 따져가며 선택을 하면, 그 사람은 "최선을 다해 게임을 진행하였다"라고 할 수 있다.

 

만약 배열 [6, 2, 7, 3] 이 있다고 해보자.

Alice는 짝수 중 가장 큰 수 6을 선택하면, +6점을 얻을 수 있다. 그렇다면 Bob은 옳구나! 하며 7을 선택해 가져 갈 것이다. 이렇게 되면 Bob은 Alice보다 +1점 이득을 본 셈이 된다.

하지만 만약 첫 턴에서 홀수 중 가장 큰 수 7을 선택하면, Bob은 얻을 수 있는 7점을 잃게 되는 셈이 된다. 방금 전 Alice의 선택이 Bob에게 -7만큼의 타격을 준 것이다. 그다음 Bob은 6을 가져갈 것이고 (안그러면 Alice가 가져갈 것이므로) 그 다음 Alice는 3, Bob은 2를 가져가 경기는 동점으로 끝나게 된다.

배열 구성만 봐도 Alice에게 불리한 게임이지만, Alice는 최선의 수를 이용해 동점으로 끝낼 수 있게 된다.

 

따라서 자신에게 +가 되던, 상대에게 -가 되던 있는 원소 중 가장 높은 것을 먹는 게 이득이다.

소스 코드1

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--){
		int n; cin >> n;
		vector<ll>v(n);
		for (int i = 0; i < n; i++) cin >> v[i];
		sort(v.begin(), v.end(), greater<int>());

		ll sum1 = 0, sum2 = 0;
		for (int i = 0; i < n; i++) {
			if (i % 2 == 0 && v[i] % 2 == 0) sum1 += v[i];
			else if (i % 2 == 1 && v[i] % 2 == 1) sum2 += v[i];
		}
		if (sum1 > sum2) cout << "Alice\n";
		else if (sum1 < sum2) cout << "Bob\n";
		else cout << "Tie\n";
	}
	return 0;
}

 

E. Correct Placement

문제

n명의 사람들이 모여 사진을 찍으려 한다.

사람들 각각은 높이, 너비 값을 가지고 있는데, 사진에 담기기 위해서 두 사람 i,j가 앞 뒤로 서 있을 때 j가 i의 앞에 오려면 두 가지 조건 중 하나를 만족시켜야 한다.

• j의 높이, 너비가 각각 i의 높이, 너비보다 작을 때
• j의 높이가 i의 너비보다 작고, j의 너비가 i의 높이보다 작을 때 (몸을 옆으로 눕힌 모양)

n명의 사람들의 높이, 너비가 각각 주어졌을 때, i번째 사람 앞에 올 수 있는 사람이 있다면 번호를 적고 (아무나)

없다면 -1을 출력하라. 

 

풀이1 (upsolving)

gravekper님의 풀이를 보고 작성하였습니다. (www.youtube.com/watch?v=iANozLL256s)

 

보통 이렇게 정렬하는 문제에서 위와 같이 높이 x 너비를 바꿀 수 있다면 (눕힐 수 있으므로)

큰 것은 큰 것끼리, 작은 것은 작은 것끼리 비교하는 것이 유리하다. 위 문제에서도 동일하게 적용될 수 있는데,

높이, 너비와 상관없이 큰 수를 높이로, 작은 수를 너비로 고정을 해둔 채 높이를 오름차순으로 정렬을 해보자. 

ex. (1,3) -> (3,1) , (2,4) -> (4,2)

 

이처럼 정렬을 했을 때 얻을 수 있는 이점은 다음과 같다.

높이 기준으로 정렬을 한 후, i번째 사람과 i+1번째 사람이 있다고 해보자.

i번째 사람은 (h1, w1), i+1번째 사람은 (h2, w2)의 높이와 너비를 가지고 있다.

 

만약 h1 = h2 일 때, i번째 사람은 절대 i+1번째 사람 앞으로 올 수 없다. (w2는 h1보다 작거나 같을 것이므로)

 

만약 h1 < h2 일 때는 너비만 비교하면 된다. w2 > w1 이면 앞으로 올 수 있고, w2 ≤ w1 이면 앞으로 못 온다는 의미이다.

여기서 너비만 비교하면 된다는 게 정말 중요한 키 포인트인데, 그렇지 않다면 사람을 눕혀서 비교해야 한다는 의미이다. 물론 h1 < h2 이므로 w1 < h2는 반드시 성립한다. (사전에 높이 > 너비로 정렬을 하였으므로)

하지만 그다음 h1과 w2를 비교하는 것이 좋은 선택인가? 하면 그렇지 않다.

어차피 h1 < h2이므로 h1보다 더 작은 w1과 w2를 비교하는 것이 이득이기 때문이다.

 

따라서, 정렬을 해놓은 후, 높이가 바뀌는 순간(이전 높이보다 커진 순간)이 나타나면, 그때까지 나온 너비 중 가장 작은 너비와 지금의 너비를 비교해서 지금이 더 크다면 비교 대상이 된 사람의 번호를 지금 사람 앞에 저장하고, 아니면 어차피 높이가 작은 사람들 중 더 넓이가 작은 사람은 없기 때문에 -1을 그대로 유지하면 된다.

 

만약 높이가 바뀌지 않았다면, 높이가 작은 사람들 중 너비가 작은 사람들을 비교하면 된다.

소스 코드1 (upsolving)

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--){
		int n; cin >> n;
		// (높이, 너비, 번호)
		vector<pair<pair<int, int> , int> >v(n);
		for (int i = 0; i < n; i++) {
			cin >> v[i].first.first >> v[i].first.second;
			if (v[i].first.first < v[i].first.second) swap(v[i].first.first, v[i].first.second);
			v[i].second = i;
		}
		// 높이 기준 오름차순 정렬
		sort(v.begin(), v.end());
		// 정답 배열 초기화
		vector<int>ans(n, -1);


		int last_h = -1;
		int last_minw = 1e9; // 현재 같은 높이의 사람들 중 가장 작은 너비
		int total_minw = 1e9; // 현재 높이보다 작은 사람들 중 가장 작은 너비
		int last_pos = -1; // last_minw를 갖는 사람의 번호
		int total_pos = -1; // total_minw를 갖는 사람의 번호

		for (int i = 0; i < n; i++) {
			int h = v[i].first.first;
			int w = v[i].first.second;
			int pos = v[i].second;

			// 높이가 달라진 경우, last 변수들 변경
			if (last_h != h) {
				if (total_minw > last_minw) {
					total_minw = last_minw;
					total_pos = last_pos;
				}

				last_h = h;
				last_minw = 1e9;
				last_pos = -1;
			}
			// 현재 너비가 토탈보다 크면 정답 수정
			if (w > total_minw) {
				ans[pos] = total_pos + 1;
			}
			if (last_minw > w) {
				last_minw = w;
				last_pos = pos;
			}
		}
		for (int i = 0; i < n; i++) cout << ans[i] << " ";
		cout << "\n";
	}
	return 0;
}