BOJ_25629_홀짝 수열 (C++)

[Bronze III] 홀짝 수열 - 25629

문제 링크

성능 요약

메모리: 2020 KB, 시간: 0 ms

분류

애드 혹, 수학

제출 일자

2024년 12월 15일 23:54:58

문제 설명

길이가 $N$인 수열의 $i(1 \le i \le N)$번째 원소를 정수 $a_i(1\le a_i \le 100)$라고 하자. 동훈이는 이 수열을 잘 정렬해서 홀짝 수열로 만들고 싶다. 어떤 수열이 홀짝 수열이 되려면 다음 조건을 만족해야 한다.

1. 수열의 홀수번째 원소는 모두 홀수여야 하고, 순서대로 나열했을 때 감소하지 않아야 한다. \(a_1 \le a_3 \le a_5 \le a_7 \le ...\) 
2. 수열의 짝수번째 원소는 모두 짝수여야 하고, 순서대로 나열했을 때 감소하지 않아야 한다. \(a_2 \le a_4 \le a_6 \le a_8 \le ...\) 

다음과 같은 수열은 홀짝 수열이다. $[1, 2, 1], [3], [5, 4]$ 그러나 다음과 같은 수열은 홀짝 수열이 아니다. $[3, 2, 1], [2, 2], [5, 4, 7, 2]$ 

  $[3, 2, 1]$의 홀수번째 원소들을 순서대로 나열하면 $[3, 1]$인데, 감소하기 때문에 홀짝 수열이 아니다.

$[2, 2]$는 첫 번째 원소가 홀수가 아니므로 홀짝 수열이 아니다.

 $[5,4,7,2]$의 짝수번째 원소들을 순서대로 나열하면 $[4, 2]$인데, 감소하기 때문에 홀짝 수열이 아니다.

길이 $N$의 수열 $a_1,a_2,…a_N$이 주어졌을 때, 이 수열을 잘 정렬한다면 홀짝 수열로 만드는 것이 가능할까?

입력

첫째 줄에 수열의 길이 $N(1\le N \le 100)$이 주어진다.

둘째 줄에 $a_1, a_2, …, a_N$이 주어진다. 수열의 $i$번째 원소는 정수 $a_i(1\le a_i \le 100)$이다.

출력

주어진 수열을 잘 정렬해서 홀짝 수열로 만들 수 있다면 1을, 어떻게 정렬하더라도 홀짝 수열로 만들 수 없다면 0을 출력한다.

문제 풀이

그냥 수열 개수로 정할 수 있다. 시작이 1이므로 홀수가 같거나 1커야하고 이를 전체 길이 홀짝 나눠서 생각해보자. 길이가 짝수면 홀짝 딱 맞게 진행되므로 odd-even이 0이고, 길이가 홀수면 홀수가 1개 많으므로 odd-even==1이다!

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

void solve() {
    int N, odd = 0, even = 0;
    cin >> N;
    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
        if (num % 2 == 0)
            even++;
        else
            odd++;
    }
    int res = 0;
    if (N % 2 == 0) {
        res = odd == even ? 1 : 0;
    } else {
        res = odd - even == 1 ? 1 : 0;
    }
    cout << res << "\n";
}

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

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    // cin >> tt;    // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}