[코드포스/Contest] Codeforces Round #647 (Div. 2)

클릭하면 코드포스 페이지로 이동합니다.

---

 

#647 후기

 

평소에 잘 쓰지 않는 XOR 연산이나 2진수 연산이 나와서 부족함을 많이 느낄 수 있는 대회였다. 이런 부분을 보완해야겠다고 생각이 들었다.

 

---

 

#647 문제

  A번 Johnny and Ancient Computer - 성공

 

정수 a, b가 주어진다. 해야 할 일은 a를 b로 바꾸는데 다음과 같은 작업을 시도할 수 있다.
a에 {2, 4, 8, 1/2, 1/4, 1/8} 중 하나를 곱한다.
a를 b와 같게 만들기 위한 최소 횟수를 출력하여라.

 

곱할 수 있는 수는 모두 2의 제곱수이다.

 

즉 a * (2^n) = b인 n값을 찾는게 문제의 폭표이다.

 

계산의 편의성을 위하여, b가 a보다 크다고 가정하면,

 

2^n = b / a 인 n을 찾아야 하고, n이 정수여야하므로 b / a가 정수이고, 2의 제곱수여야한다.

 둘 중 하나라도 해당되지 않으면 만족하는 n이 존재하지 않으므로 답은 -1이다.

 만족한다면 2의 개수 n은 log2(b / a)로 표현 가능하다.

 

이제 2가 아닌 4(2의 제곱), 8(2의 세제곱)으로 계산했을 경우를 처리하면 된다.

 

2를 세번 곱한것이 8을 한번 곱한것과 같고, 두번 곱한것이 4를 한번 곱한것과 같다.

 

이를 처리해서 출력하면 된다.

 

아래는 정답코드이다.

 

#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))

// 기본설정
typedef long long ll;
using namespace std;

int main(void) {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int tc;
	cin >> tc;

	while(tc--) {
		ll a, b, c, temp, cnt = 0;
		cin >> a >> b;
		if(a == b) {
			cout << "0\n";
			continue;
		}

		if(a > b) {
			if(a % b == 0 && POW2(a/b)) {
				c = log2(a/b);
			} else {
				cout << "-1\n";
				continue;
			}
		} else {
			if(b % a == 0 && POW2(b/a)) {
				c = log2(b/a);
			} else {
				cout << "-1\n";
				continue;
			}
		}
		
		if(0 < c / 3) {
			cnt += c / 3;
			c -= 3 * (c / 3);
		}
		if(0 < c / 2) {
			cnt += c/ 2;
			c -= 2 * (c / 2);
		}
		if(0 < c) cnt += c;
		
		cout << cnt << "\n";
	}

	return 0;
}

---

  B번 Johnny and His Hobbies - 성공

길이가 n인 숫자 배열이 주어진다. 배열 각각의 원소에 정수 k를 XOR 연산을 진행했을 때, 처음 배열과 동일한 원소를 가지고 있게 하는 정수 k의 최소값을 출력하여라. 만약 정수 k가 존재하지 않으면 -1을 출력한다.

 

처음에 어떻게 해결해야 하나 고민을 오래 했었다.

 

그러다가 놓친 부분이 있었는데, 바로 테스트케이스와 배열의 길이, 그리고 k의 값이 1024 부근까지만 사용한다는 점이였다.

 

크기가 생각보다 작으므로, k값을 1부터 증가시키면서 원본 배열과, XOR 연산을 진행 한 배열을 정렬된 상태로 비교해서, 만약 같은 배열이 된다면 그때의 k값을 출력하고, 1024까지 증가했는데 같은 배열을 찾지 못한 경우에 -1을 출력했다.

 

코드로 구현하면,

#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))

// 기본설정
typedef long long ll;
using namespace std;

int main(void) {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int tc;
	cin >> tc;

	while(tc--) {
		int n, ans = 0;
		cin >> n;
		vector<int> arr, comp;
		for(int i = 0; i < n; i++) {
			int temp;
			cin >> temp;
			arr.push_back(temp);
		}
		sort(arr.begin(), arr.end());
		for(int i = 1; i < 1024; i++) {
			comp = arr;
			for(int j = 0; j < arr.size(); j++) {
				comp[j] = comp[j] ^ i;
			}
			sort(comp.begin(), comp.end());
			if(comp == arr) {
				ans = i;
				break;
			}
		}
		if(ans == 0) {
			cout << "-1\n";
		} else {
			cout << ans << "\n";
		}
	}

	return 0;
}

---

C번 Johnny and Another Rating Drop - 성공

정수 n이 주어진다. 해야 할 일은, 0부터 정수 n까지 이진법으로 표현했을 때, 인접한 두 수의 각 비트마다 다른 부분의 횟수를 모두 더한 값을 출력하라.

 

처음에 노트에 0부터 쭉 써보면서, 어떤 규칙이 있을 것 이라고 생각해서 규칙을 찾는데 집중했다.

 

정수	정수 -> 이진수	다른 부분의 개수	누적 횟수
0	0000	-	-
1	0001	1	1
2	0010	2	3
3	0011	1	4
4	0100	3	7
5	0101	1	8
6	0110	2	10
7	0111	1	11
8	1000	4	15
9	1001	1	16

 

위의 표를 보면 정수 1일때 값을 0과 1 사이의 다른 부분의 개수라고 놓았을 때,

 

2의 제곱수들을 간격으로 일정한 규칙을 가지고 있다.

 

n번째 제곱수 2^n, (n + 1)번째 제곱수 2^(n + 1)이 있다고 가정하면,

 

정수 (2^n + 1)부터 정수 2^(n + 1) 까지의 다른 부분의 개수는, 정수 1부터 정수 (2^n - 1) 까지의 다른 부분의 개수에 마지막 2^(n + 1)번째마나 다르다.

 

예를들어 설명하면, 5 ~ 8 범위의 다른 부분의 개수를 알고싶다면, 1 ~ 3 범위와 5 ~7 범위가 같고, 마지막 8일때만 처리를 하면 된다. (1 ~ 4 : 1, 2, 1, 3 / 5 ~ 8 : 1, 2, 1, 4)

 

그리고 현재 숫자가 2의 제곱수 2^n이라고 하면, 현재 다른 부분의 개수는 (n + 1)개 이고, 이때까지의 누적 횟수는 2^(n + 1) - 1로 표현이 된다.

 

즉,

 

정수	정수 -> 이진수	다른 부분의 개수	누적 횟수
2^N	10...00	N + 1	2^(N + 1) - 1

 

이를 DP를 이용하여 memo배열을 선언하였다.

 

memo[n]은 정수가 2^n일때, 그 이전까지의 누적 횟수를 기록하는 배열이다.

 

즉 memo[n] = pow(2, n + 1)이다.

 

그래서 우리가 원하는것은, 어떤 정수까지의 누적 횟수를 구하는 것이다.

 

그래서 2의 제곱수를 기준으로 정수를 줄여나가는 방법을 사용할 것이다.

 

19까지의 누적 횟수를 구한다고 가정해보면,

 

처음에 19 이하의 가장 큰 2의 제곱수인 16의 횟수를 더한다. 즉, cnt += memo[4]

이제 17, 18, 19일때의 횟수를 구해야 한다.

하지만 위에서 17 ~ 31까지의 다른 부분의 개수는 1 ~ 15까지의 다른 부분의 개수와 같다는 것을 알았다.

그래서 문제는 다시, 3까지의 누적 횟수를 구하는 것으로 볼 수 있다.

 

그래서 이러한 과정을 반복해서, 남은 수가 0만 남게되면, cnt를 출력했다.

 

아래는 정답코드이다.

 

#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))

// 기본설정
typedef long long ll;
using namespace std;

int main(void) {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int tc;
	cin >> tc;

	while(tc--) {
		ll n, cnt = 0, c = 1, cp = 0;
		cin >> n;
		vector<ll> memo;
		while(c <= n) {
			memo.push_back(pow(2, cp + 1) - 1);
			c *= 2;
			cp += 1;
		}

		c /= 2;
		cp--;
		cnt += memo[cp];

		ll rest = n - c;
		while(0 < rest) {
			ll cur = 1, curp = 0;
			while(cur <= rest) {
				cur *= 2;
				curp++;
			}
			cur = cur / 2;
			curp--;
			rest -= cur;
			cnt += memo[curp];
		}

		cout << cnt << "\n";
	}

	return 0;
}