취미로 코딩하기

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

이번에 볼 문제는 백준 10009번 문제인 Loteria 2이다.
문제는 아래 링크를 확인하자.

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

공에 적힌 수가 두 가지 이상일 경우 어떤 수를 바꾼다면 양 옆의 수와 다른 수를 항상 골라 그 수로 바꿀 수 있음을 관찰하자. 따라서 이 경우 고른 수를 왼쪽부터 살피면서 같은 수가 적힌 공이 연속으로 있는 지점을 발견할 때마다 오른쪽 공을 양 옆 수와 다른 수를 적어넣는 것으로 최소 횟수의 수정으로 조건을 만족하는 수열을 만들 수 있음을 알 수 있다.

공에 적힌 수가 두 가지뿐인 경우를 생각해 보자. 두 수를 1과 2라고 하면 가능한 수열은 1과 2가 교대로 등장하는 수열 두 가지(1로 시작, 2로 시작)뿐이다. 따라서 이 두 가지 중 어떤 수열로 바꾸는 것이 비용이 덜 드는지를 확인해 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

int N, K;
int A[500000];
int cnt1, cnt2;

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

	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> A[i];
	if (K == 2) {
		for (int i = 0; i < N; i++) {
			if (i & 1) {
				if (A[i] == 1) cnt1++;
				else cnt2++;
			}
			else {
				if (A[i] == 1) cnt2++;
				else cnt1++;
			}
		}
		cout << min(cnt2, cnt1);
	}
	else {
		int old = 0, ans = 0;
		for (int i = 0; i < N; i++) {
			if (A[i] == old) ans++, old = 0;
			else old = A[i];
		}
		cout << ans;
	}
}