[CF] Round #695 (Div. 2) _ 210108

(2021년 1월 9일에 작성한 글입니다.)

 

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

 

A.

처음에는 9876543210987... 이렇게 출력하는 건 줄 알았다

근데 웃긴건 내가 잘못 해서

첫 번째 제출에 if(num == 0) num = 9;

이렇게 해서 9876543219876... 이렇게 출력되게 됐고

이거 때문에 틀린 줄 알고 수정해서 다시 냈는데 또 틀렸다.

그래서 생각해보니까...

앞에서 두 번째 숫자가 8이 될 때 break 해서

9890123456789012345...

이렇게 되는게 최대다..

깨닫는데 시간이 좀 걸렸다

다 비슷한 상황이었다...ㅎ

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int TC;

	cin >> TC;
	while (TC--) {
		int N;
		int num;
		string s = "989";
		int i;

		cin >> N;
		if (N <= 3) {
			for (i = 0; i < N; i++) {
				cout << s[i];
			}
			cout << ENDL;
			continue;
		}
		
		num = 0;
		cout << 989;
		for (i = 3; i < N; i++) {
			cout << num;
			num++;
			if (num == 10) {
				num = 0;
			}
		}

		cout << ENDL;
	}

	return 0;
}

​

C.

이건 종료 후에 풀었는데

아이디어를 떠올리기가 쉽지 않다.

​

서로 더하고 하다 보면

값 * 2배만큼 sum에서 빠지게 되는 수가 생길수밖에 없다.

그래서 그 수가 뭐가 될것인가가 문제인데

​

1) 빼는 수가 두 줄에서 하나씩 나오는 경우

a/b, a/c, b/c 이렇게 둘 씩 묶어서 각각의 최솟값의 합의 두 배를 빼면 된다.

ex. 7 5 4 / 2 9 / 7 1 -> sum = 35, 최소는 2 + 1 -> 답은 35 - 2 * (2 + 1) = 29

2) 빼는 수를 한 줄에서만 뽑는 경우

a, b, c 중 하나를 모두 빼면 됨

ex. 1 2 3 / 10 / 20 -> sum = 36, 첫 번째 줄을 모두 빼면 -> 답은 36 - 2 * (1 + 2 + 3) = 24

​

1)의 경우에는

수들을 다 정리한 다음에 둘을 합칠 수 있기 때문에 가능하지만

2)의 경우에는 한 줄만 남긴 후에 서로서로 합치도록 할 수 없기 때문에

한 줄에서만 빼기로 했다면, 그 줄은 모두 빠질 수 밖에 없다.

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N[3];
	vector<vector<ll>> arr(3);
	ll sum[3] = { 0 }, minus = LLONG_MAX;
	int i, j;

	for (i = 0; i < 3; i++) {
		cin >> N[i];
		arr[i].resize(N[i] + 5);
	}
	for (i = 0; i < 3; i++) {
		for (j = 0; j < N[i]; j++) {
			cin >> arr[i][j];
			sum[i] += arr[i][j];
		}
		sort(arr[i].begin(), arr[i].begin() + N[i]);
	}

	for (i = 0; i < 3; i++) {
		minus = min(minus, sum[i]);
	}
	minus = min(minus, arr[0][0] + arr[1][0]);
	minus = min(minus, arr[1][0] + arr[2][0]);
	minus = min(minus, arr[0][0] + arr[2][0]);

	cout << sum[0] + sum[1] + sum[2] - 2 * minus << ENDL;

	return 0;
}