[백준 28323] 2023 정올 2차 초등부 "불안정한 수열"

문제 출처 : https://www.acmicpc.net/problem/28323

28323번: 불안정한 수열

 

이 문제는 2023년 정보올림피아드 초등부 2차 1번 문제 였습니다.

수열 A에서 이웃한 자연수의 합을 구했을 때 항상 홀수인 수열 B를 구하는 문제 입니다. 문제를 어떻게 풀어야 할지 감이 잘 잡히지 않는다면 조합을 구하고 그 중 답이 있는지 확인하면 됩니다. 그럼 100점은 맞지 못하더라도 부분 점수를 얻을 수 있습니다.

정보 올림피아드는 시간 관리가 중요합니다. 따라서 어렵게 느껴진다면 일단 부분 점수라도 맞고 시작하길 바랍니다.

문제 이해하기

문제가 길어 이해하기 쉽지 않습니다. 하지만 하나하나 따라가다보면 무슨 문제인지 이해할 수 있습니다. 주어진 수열 A에서 몇개의 숫자를 순서대로 뽑아 앞, 뒤 숫자를 더해 모두 홀수인 가장 긴 수열을 찾는 문제 입니다. 이 문제도 얼핏 보면 DP로 풀어야 겠다는 생각이 듭니다. 하지만 조금 더 생각해보면 쉽게 문제를 해결할 수 있습니다.

홀수가 만들어 지는 경우

이 문제의 핵심은 홀수가 언제 만들어지는지 정확히 이해해야 합니다.

1. 홀수 + 홀수 = 짝수
2. 짝수 + 짝수 = 짝수
3. 홀수 + 짝수 = 홀수
4. 짝수 + 홀수 = 홀수

숫자들을 계산할 필요 없이 홀수와 홀수를 더하거나, 짝수와 짝수를 더하면 무조건 짝수가 나오게 됩니다. 3 + 3은 6으로 짝수이고, 2 + 2 도 4로 짝수임을 쉽게 알 수 있습니다.

그에 반해 홀수와 짝수를 더하거나 짝수와 홀수를 더하면 홀수가 나옵니다. 3 + 4는 7으로 홀수이고, 6 + 7은 13으로 홀수 입니다. 즉 우리는 수열 A에서 홀수와 짝수가 번갈아 가장 길게 나오는 수열을 찾으면 되는 문제가 됩니다.

알고리즘 구현하기

1. 첫 번째 수가 홀수인지 짝수인지 확인 합니다.
2. 두 번째 수가 첫 번째 수와 홀짝이 다르다면 수열 B의 길이를 1 늘려주고 세 번째수는 다음 홀짝을 찾습니다.
3. 두 번째 수가 첫 번째 수와 홀짝이 같다면 다음으로 넘어갑니다.
4. 위 코드를 수열 A의 끝까지 확인 합니다.

좀 어렵게 느껴질 수 있지만 하나하나 따져보면 간단합니다. 첫 번째 수가 홀수라면 다음에는 짝수를 찾습니다. 짝수를 찾고 나면 다음에는 홀수를 찾습니다. 이렇게 홀짝홀짝을 찾아나가면 길이를 구하면 되는 문제 입니다.

코드 작성

입력 받기

N = int(input())
A = tuple(map(int, input().split()))

수열 A의 길이 N과 수열 A를 입력 받습니다. A의 값은 변경이 되지 않기 때문에 tuple로 받았습니다.

첫 번째 수 확인

check = A[0] % 2

첫 번째 수가 홀수인지 짝수인지 확인합니다. check값이 0이면 짝수이고, 1이면 홀수인 것입니다. 첫 번째 숫자에 맞게 다음 홀짝을 찾아주면 됩니다.

수열 A의 홀짝 확인

cnt = 1
for a in A[1:]:
    if a % 2 == 1 - check:
        cnt += 1
        check = 1 - check

print(cnt)

수열의 길이가 1인 경우도 불안정한 수열입니다. 첫 번째 숫자를 이미 확인했기 때문에 답으로 출력할 cnt 값도 1이 됩니다.

다음으로 두 번째 수부터 A를 돌면서 홀짝을 확인 합니다. 1 - check 값을 확인하면 다음 홀짝을 알 수 있습니다.

원래 check값이 짝수인 0 이라면 1 - 0 은 1이 되어 홀수를 확인할 수 있습니다. 마찬가지로 check 값이 홀수인 1이라면 1 - 1은 0으로 다음수는 짝수를 확인할 수 있습니다.

홀짝을 확인한 뒤 원하는 수가 나왔으면 cnt 값도 1 늘려주고, 홀짝도 바꿔줍니다. 이렇게 모든 숫자를 확인한 뒤 cnt값을 출력하면 원하는 결과를 얻을 수 있습니다.

전체 코드

전체 코드를 확인해 보겠습니다.

N = int(input())
A = tuple(map(int, input().split()))

check = A[0] % 2

cnt = 1
for a in A[1:]:
    if a % 2 == 1 - check:
        cnt += 1
        check = 1 - check

print(cnt)

별로 어렵지는 않은 문제이지만 시험에 당황하면 어렵게 느껴질 수 있습니다. 이런 문제들을 많이 풀어보며 자신감을 기르면 시험에서도 당황하지 않고 원하는 결과를 얻을 수 있을 것입니다.