[CF] Round #669 (Div. 2) _ 200908

(2020년 9월 10일에 작성한 글입니다.)

 

Dashboard - Codeforces Round #669 (Div. 2) - Codeforces

 

A.

코포 스타일의 문제에 빨리 익숙해져야 할 것 같다. 그러려면 문제를 많이 풀어봐야 되겠지.

A에서 시간을 많이 쓰는 걸 해결해야 할 듯.

0이랑 1만 등장하기 때문에

만약 전체에서 0의 개수가 더 많으면, 그냥 그 개수만큼 0을 출력하고

1이 더 많으면 1을 짝수개만 남겨두고 출력하면 된다.

짝수개를 남겨두는 방법은,

현재 1의 개수가 짝수면 그대로 남겨두고, 홀수면 1개를 없애고.

이때 1개를 없앨 때, 남아있는 1의 개수가 K/2 이상이어야 하는데

무조건 그렇게 된다. 왜냐하면 1이 0보다 많은 상태이고

그럼 최소 K/2+1이기 때문.

이걸 한참 돌아가서 30분동안 풀었어... 몇 번이나 틀리고.

​

이렇게... 코포 A에서는

괜히 예제를 복잡하게 만들어서 되게 복잡한 문제처럼 보이게 하는데

알고보면 진짜 단순하게 출력하면 되는.. 그런 문제가 많다.

여기에 익숙해져야 할 듯.

A에서부터 시간을 줄이는 연습을 해야겠다.

​

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	int N;
	int i;
	int temp;

	cin >> T;
	while (T--) {
		cin >> N;
		vector<int> arr(N);
		vector<int> sum(2);

		pair<int, int> cur;
		for (i = 0; i < N; i++) {
			cin >> temp;
			arr[i] = temp;
			sum[temp]++;
		}
		
		if (sum[0] >= sum[1]) {
			cout << sum[0] << '\n';
			for (i = 0; i < sum[0]; i++) {
				cout << 0 << ' ';
			}
			cout << '\n';
		}
		else {
			if (sum[1] % 2) {
				sum[1]--;
			}
			cout << sum[1] << '\n';
			for (i = 0; i < sum[1]; i++) {
				cout << 1 << ' ';
			}
			cout << '\n';
		}
	}

	return 0;
}

 

B.

갖고 있던 최대공약수 구하는 코드 이용해서 금방 풀었다.

일단 무조건 가장 큰 값이 맨 앞에 와야 하고

그 뒤로는 GCD 계속 구해가면서 GCD가 가장 큰 걸 그 뒤에 넣고

그리고 GCD가 1이 되면 나머지는 순서가 상관 없게 됨.

int gcd(int k, int l)
{
	return l ? gcd(l, k % l) : k;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	int N;
	int cur_num, cur_gcd;
	int gcd_;
	int max_, max_i;
	int i;

	cin >> T;
	while (T--) {
		cin >> N;
		vector<int> arr(N);
		for (i = 0; i < N; i++) {
			cin >> arr[i];
		}
		sort(arr.begin(), arr.end(), greater<int>());

		vector<bool> used(N);
		used[0] = true;
		cout << arr[0] << ' ';

		cur_num = cur_gcd = arr[0];
		for (int cnt = 1; cnt < N; cnt++) {
			max_ = 0;
			for (i = 1; i < N; i++) {
				if (!used[i]) {
					gcd_ = gcd(cur_gcd, arr[i]);
					if (max_ < gcd_) {
						max_ = gcd_;
						max_i = i;
					}
				}
			}
			used[max_i] = true;
			cur_num = arr[max_i];
			cur_gcd = max_;
			cout << cur_num << ' ';

			if (cur_gcd == 1 && cnt != N - 1) {
				for (i = 0; i < N; i++) {
					if (!used[i]) {
						cout << arr[i] << ' ';
					}
				}
				break;
			}
		}

		cout << '\n';
	}

	return 0;
}