CodeForces #899 (Div. 2) Write-Up (A ~ D) 작성중.

서론

딱 2년 만에 다시 해본다.

문제 풀이가 너무 감으로 이뤄지고 뭔가 좀 그렇다 싶었는데 끝나고 보니까 모든 문제가 다 그리디였다.

그리디도 진짜 문제 많이 풀어봐야 할 것 같다. 구성적 해 문제도 너무 못 푼다.

accepted 글자를 봐도 깔끔하게 풀었다는 느낌을 받을 수가 없다.

A/B 2솔딱으로 끝났다.. 

특히 B번 난이도는 아직 안적혀서 모르겠는데 시간 이거에 다 뺐다. 인덱스가 복잡하고 자꾸 헷갈려서 적어가며 했어야하는데 이상한 자존심 때문에 암산으로 꾸역꾸역하다가 시간 다 날렸다.

 

풀이

A. https://codeforces.com/contest/1882/problem/A

Problem - A - Codeforces

풀이

주어진 배열과 같은 인덱스에 같은 값이 오지 않도록 같은 크기의 증가하는 수열을 뽑는 문제이다.

배열 인덱스를 증가시키며 주어진 배열과 값이 같을 경우 +1만 하고 +1된 값들은 따로 변수에 저장해 중첩시키면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
using namespace std;
using ll = long long;

int main() {
	int tc; cin >> tc;
	while (tc--) {
		int n; cin >> n; vector<int> arr(n + 1);
		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
		}
		int pv = 0; vector<int> dp;
		for (int i = 1; i <= n; i++) {
			if (arr[i] == i + pv) pv++;
			dp.push_back(i + pv);
		}		
		cout << dp[n - 1] << "\n";
	}
	
	return 0;
}

---

B. https://codeforces.com/contest/1882/problem/B

Problem - B - Codeforces

풀이

여러 부분 집합 배열이 입력으로 주어지고 모든 숫자가 나오지 않도록 하는 선에서 가장 많은 숫자를 가진 합집합을 구하는 문제이다.

입력 배열과 더불어 숫자 1~50 까지 그 숫자가 등록되어있는 배열 번호를 저장하는 배열 tb를 사용한다.

숫자를 하나씩 제거하며 제거 대상 숫자를 포함하는 배열에 있는 숫자들을 포함하는 배열이 제거 대상 숫자를 포함하는 배열에 포함되면 제거 대상 숫자를 제거하기 위해서 추가로 제거해야하는 숫자인 것이다.

 

쉽게 다시 설명하면 숫자를 제거하려면 그 숫자를 포함하는 배열들을 모두 제거해야 하는데 이 때 그 제거되는 배열들 속에 있는 숫자들이 함께 제거될지 여부를 검사한다고 보면 된다.

 

아래와 같은 예제 입력이 있다고 해보자.

5
1 1
3 3 6 10
1 9
2 1 3
3 5 8 9

총 숫자는 1, 3, 5, 6, 8, 9, 10 이다.

가장 처음 숫자인 1을 제거해보자.

숫자 1 을 포함하는 배열은 1번 4번 배열이다.

1번 배열은 숫자 1밖에 없고 숫자 1은 제거가 확정된 숫자이기 때문에 생략한다.

따라서 1번 배열을 제거하면 숫자 1만 제거되고 다른 숫자에 영향이 없다.

그 다음은 4번 배열이다. 

4번 배열은 숫자 1, 3 이 있고 숫자 1은 이미 제거가 확정되었으므로 생략한다.

숫자 3을 포함하는 배열은 2번, 4번 배열이다. 배열 2번은 숫자 1을 제거했을 때 제거 대상 배열 목록 에 포함되지 않으므로 배열 4를 제거해도 숫자 3은 제거되지 않는다.

따라서 숫자 1을 제거할 때 추가적으로 삭제되는 숫자는 없다. 만약 배열 2가 없었다면 숫자 3도 삭제되어야하므로 숫자 1을 제거할 때 숫자 3도 같이 삭제됐을 것이다.

 

위와 같은 방식으로 가장 삭제되는 숫자가 적을 때의 삭제 개수를 찾고 전체 배열 크기 7에서 빼면 답을 구할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
using namespace std;
using ll = long long;
int main() {
	int tc; cin >> tc;
	while (tc--) {
		int n; cin >> n; vector<vector<int>> arr(n + 1); vector<vector<int>> tb(51);		
		for (int i = 1; i <= n; i++) {
			int t; cin >> t;
			for (int j = 1; j <= t; j++) {
				int p; cin >> p; arr[i].push_back(p); tb[p].push_back(i);
				
			}
		}	
		int cnt = 0; int mn = 2100000000;
		for (int i = 1; i <= 50; i++) {
			if (tb[i].size() > 0) {
				cnt++;
				int s = 0;
				vector<int> check(51);
				for (int j = 0; j < tb[i].size(); j++) {
					for (const int& ap : arr[tb[i][j]]) {
						if (check[ap] == 1) continue;
						check[ap] = 1;
						int sign = 0;
						for (int k = 0; k < tb[ap].size(); k++) {
							if (std::find(tb[i].begin(), tb[i].end(), tb[ap][k]) == tb[i].end()) {
								sign = 1; break;
							}
						}
						s += 1 - sign;
					}
				}
				mn = mn < s ? mn : s;					
			}
		}		
		cout << cnt - mn << "\n";
	}	
	return 0;
}

---

C. https://codeforces.com/contest/1882/problem/C

Problem - C - Codeforces

풀이

카드 덱에서 한장 씩 골라 제거하는데 홀수 번째 있는 카드를 제거할 경우 그 카드에 쓰여있는 점수를 먹어야 한다.

카드가 제거 된 경우 그 뒤에 있는 카드들이 앞으로 당겨진다. 카드 중에는 음수카드 도 섞여 있다.

얻을 수 있는 최대 점수를 구하는 문제다.

 

카드를 제거할 때 뒤에있는 카드들의 인덱스만 바뀌므로 현재 홀수 인덱스에 있는 카드들은 항상 점수를 먹을 수 있음이 자명하다. 뒤에서부터 차례대로 홀수 번째 카드를 골라 제거하면 앞에 있는 홀수 번째 카드들의 인덱스를 변화시키지 않으므로 모두 먹을 수 있다.

 

또한 짝수 인덱스 카드들은 현재 카드 i를 먹지 않거나 앞에 있는 홀수 카드 i-1를 먹는 경우 마찬가지로 모두 홀수 인덱스로 전환되므로 모두 먹을 수 있다. 단, 앞에 있는 홀수카드가 양수 카드였을 경우 이미 홀수 계산에서 먹었을 것이므로 양수인 경우는 제외하고 음수인 경우에만 먹어야 한다.

 

로직을 정리하면 다음과 같다.

1. 홀수 인덱스 카드들은 양수일 경우 모두 먹는다.
2. 짝수 인덱스 카드들은 뒤에서부터 ( 위에서 설명했다 시피 뒤부터 먹어야 인덱스가 변하지 않는다. ) 합을 구해가며 현재 인덱스 i번째 카드를 먹지 않은 합과 현재 인덱스 i와 그 다음의 홀수 인덱스 i-1 카드를 모두 먹은 합 중 큰 것을 고른다.
3. 마지막 짝수 인덱스까지 더했을 구한 합 중 최댓값을 골라 1에서 구한 홀수 인덱스 점수 합과 더하여 답을 구한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
#include <list>
using namespace std;
using ll = long long;
int main() {
	int tc; cin >> tc;
	while (tc--) {
		int n; cin >> n; vector<ll> arr(n + 1);
		for (int i = 1; i <= n; i++) {
			cin >> arr[i]; 
		}		
		ll sum = 0; ll mx = 0; ll es = 0;
		for (int i = n; i >= 1; i--) {				
			if (i % 2 == 1) {
				if (arr[i] > 0) {
					sum += arr[i];
				}
			}
			else {							
				ll s  = es > es + (arr[i - 1] < 0 ? arr[i - 1] : 0) + arr[i] ? es : es + arr[i] + (arr[i - 1] < 0 ? arr[i - 1] : 0);
				if (arr[i] > 0) {
					es += arr[i];						
				}
				mx = mx > s ? mx : s;
			}
		}
		cout << sum + mx << "\n";
	}
	return 0;
}

---

D. https://codeforces.com/contest/1882/problem/D

Problem - D - Codeforces

풀이

우선 정점 하나일 때만 생각하고 풀어보자.

최종 목적이 루트 정점을 제외한 모든 정점의 값이 같아지게 하는 것이고 루트 정점은 부모가 없기 때문에 값을 변경할 수 없다. 따라서 모든 정점의 값을 같게 한다는 것은 루트 값으로 바꾼다는 뜻이 된다.