[백준 28323번] 불안정한 수열 (C++) (한국정보올림피아드 KOI 2323 2차대회)

1. 문제

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

28323번: 불안정한 수열

이미지 예시

2023년 정보올림피아드 초등부 1번 문제이다.

 

2. 풀이

문제에서 정의한 불안정안 수열이란 이웃한 두 숫자의 합이 모두 홀수인 수열을 말한다.

자연수의 배열이 주어졌을 때 최대 몇개의 숫자로 불안정한 수열을 만들 수 있는지 구하는 문제이다.

 

불안정한(이웃한 두 수의 합이 모두 홀수인) 수열을 만들려면 수열을 탐색하며 이웃한 두 수의 합이 짝수가 되는 경우를 제거해주어야 한다. 

 

 홀수와 짝수의 성질을 먼저 살펴보자.

짝수 + 짝수 = 짝수
홀수 + 홀수 = 짝수
짝수 + 홀수 = 홀수

 

위의 경우에서 이웃한 숫자가 둘다 홀수 또는 둘다 짝수일 경우 불안정한 수열을 만들 수 없으므로 이 경우를 제거해주면 된다. 배열을 입력받은 뒤 비교하며 탐색하여 하나씩 제거해줄 수도 있지만 자료구조의 스택을 이용하면 더 간단한 방법으로 풀 수 있다.

 

숫자를 입력받을 때 바로 전에 입력받은 숫자와 비교해보고 둘 다 같은 종류의 수이면 입력받지 않는다.

---

알고리즘

1. 스택이 비어있으면 입력받은 값을 넣는다.
2. 전에 입력받은 값과 현재 입력받은 값을 비교하여 둘 다 같은 종류(둘 다 짝수 또는 둘 다 홀수)이면 현재 입력받은 값을 넣지 않는다.
3. 2의 과정을 반복한다.
4. 마지막에 스택에 넣어진 숫자의 크기가 만들 수 있는 최대 불안정한 수열의 크기이다.

 

3. 코드

#include<iostream>
#include<vector>

using namespace std;

vector<int> vec;

int main(void) {
	int N;
	bool odd;
	cin >> N;
	while (N--) {
		int num;
		cin >> num;

		if (vec.empty() || num % 2 != odd) vec.push_back(num);
		if (num % 2) odd = true;
		else odd = false;
	}

	cout << vec.size();
	return 0;
}