취미로 코딩하기

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

이번에 볼 문제는 백준 28858번 문제인 Пасьянс이다.
문제는 아래 링크를 확인하자.

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

먼저 홀수로 시작하는 수열 중 가장 긴 수열의 길이를 구해보자.

첫 홀수는 어떤 수로 골라야할까? 가장 긴 수열의 첫 항이 되는 홀수는 여러 가지 있을 수 있으나, 주어진 홀수 중 "가장 작은" 홀수로 시작하는 경우는 항상 포함되어 있다. 가장 작은 홀수로 시작하지 않는 수열이 있다면 그 수열의 첫 수를 가장 작은 홀수로 바꾸는 것으로 같은 길이의 수열을 얻을 수 있기 때문이다.

위와 같은 논리를 반복적으로 적용하면, 이 수열의 길이를 늘려나갈 때 앞서 나온 수보다 큰 수중 가장 작은 짝수와 홀수를 번갈아가면서 이어붙여나가는 것으로 구하고자 하는 수열 중 하나를 구할 수 있게 된다.

한편, 짝수로 시작하는 수열 중 가장 긴 수열의 길이도 이와 같은 방법으로 구할 수 있고, 두 길이 중 더 큰 값이 문제의 답이 될 것임을 어렵지 않게 관찰할 수 있다.

위의 내용을 구현해 문제를 해결하자.

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

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

int N;
int A[100];
int oldX = -1000000007, oldY = -1000000006;
int cntX = 0, cntY = 0;

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

	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	sort(A, A + N);
	
	for (int i = 0; i < N; i++) {
		if ((oldX + A[i]) & 1) oldX = A[i], cntX++;
		if ((oldY + A[i]) & 1) oldY = A[i], cntY++;
	}

	cout << max(cntX, cntY);
}