[Bronze III] 홀짝 수열 - 25629

문제 링크

성능 요약

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

분류

수학, 애드 혹

제출 일자

2026년 04월 25일 22:04:59

문제 설명

길이가 $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을 출력한다.

---

💡 해결 방법

💻 코드

//https://www.acmicpc.net/problem/25629
//20:43~
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define data(a) a%2 == 0
 
void check(int arr[], int len)
{//1. arr을 정렬한다. 
//2.len이 홀수라면, arr은 홀수가 (len)/2 +1, 짝수가 len/2
//3.짝이면, 홀수가 len/2, len/2개여야 한다.
//4. 정렬은 필요없고, arr에서 홀, 짝의 개수만 세자
 
 
int odd = 0; int even = 0;
    for(int i = 0; i < len; i++)
    {
    if(data(arr[i]) == 0)
        odd++;
    else even ++;
    }
 
//printf("[%d %d]", odd, even);
 
switch(data(len))
    {
    case(0)://홀인 경우
    {
        if(odd == (len) / 2 + 1 && even == (len) / 2)
        {
            printf("1");
        }        
        else
            printf("0");
        break;
    }
    default://짝인 경우
    {
        if(odd == (len) / 2 && even == (len) / 2)
        {
            printf("1");
        }          
        else
            printf("0");
    }
    }
 
}
 
 
int main()
{
    int len = 0; scanf("%d", &len);
    int *arr = (int*)malloc(sizeof(int)*len);
    for(int a = 0; a < len; a++)
    {
        scanf("%d", &arr[a]);
    }
 
    check(arr, len);
 
 
    return 0;
}