취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 10330번 문제인 과일 서리이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/10330 

지문에 서술되어 있듯이, 연속 코드의 형태로 주어진 문자열은 '0'으로 시작하는 것과 '1'로 시작하는 것 두 종류가 있다. 각 문자열에 대하여 (1) 비트의 순열로 주어진 문자열로부터 해당 문자열을 만들 수 있는지, 그리고 (2) 그 때 필요한 연산의 수는 얼마인지를 계산해 문제를 해결하자.

어떤 문자열이 다른 문자열로 바뀔 수 있을 필요충분조건은 각 문자열을 구성하는 문자가 같은 것과 같다. (증명은 어렵지 않으므로 생략한다.)

한편, 원래의 문자열에서 같은 비트를 가진 두 인덱스 \(i<j\)에 대응되는 문자가 변환된 문자열에서 위치하는 인덱스를 각각 \(f_i\), \(f_j\)라 할 때 최종 문자열에서 \(f_i>f_j\)와 같이 변환된 경우 항상 \(f_i<f_j\)가 되게끔 변환 과정을 수정할 수 있음을 관찰하자. \(f_i>f_j\)가 되려면 두 인덱스가 가리키던 두 문자가 인접해 있던 순간이 존재해 그 둘을 직접 바꾸는 순간이 있어야하는데, 이 둘을 바꾸는 과정을 지워도 완성되는 문자열은 같다는 점을 관찰하면 위 내용을 쉽게 이해할 수 있다.

그렇다면 남은 과정은 각 비트를 대응되는 각각의 위치로 옮기는 것이다. 만약 각 문자를 옮기는 데에 대응되는 두 인덱스의 차만큼의 연산만 사용할 수 있다면 그 때의 연산의 수가 최소가 될 것임은 자명하다. 그리고 나중 문자열의 첫 문자부터 하나씩 정위치에 있게끔 연산을 차례대로 적용하면 이와 같은 횟수의 연산만을 사용해 문자열을 변환할 수 있음을 관찰할 수 있다.

더 많은 내용을 알아보고 싶다면 cp에서 자주 만나게 되는 주제인 inversion counting에 대해 조사해보자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

int N, K;
vector<int> A, B, C;
int ans = 1000000007;

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

	cin >> N >> K;
	for (int n = 0; n < N; n++) {
		int x; cin >> x;
		if (x) C.emplace_back(n);
	}
	for (int k = 0, idx = 0; k < K; k++) {
		int x; cin >> x;
		if (k & 1) {
			while (x--) {
				A.emplace_back(idx);
				idx++;
			}
		}
		else {
			while (x--) {
				B.emplace_back(idx);
				idx++;
			}
		}
	}

	if (A.size() == C.size()) {
		int val = 0, sizeA = A.size();
		for (int i = 0; i < sizeA; i++) {
			val += abs(A[i] - C[i]);
		}
		ans = min(ans, val);
	}
	if (B.size() == C.size()) {
		int val = 0, sizeB = B.size();
		for (int i = 0; i < sizeB; i++) {
			val += abs(B[i] - C[i]);
		}
		ans = min(ans, val);
	}

	cout << ans;
}