2022 한국정보올림피아드(KOI) 1차 대회 2교시 초등부

한국 정보올림피아드(KOI) 기출 문제 풀이과정을 수록합니다.

한국정보올림피아드(KOI) 기출 문제 풀이 모음

1. 빵 (초1)

제목 링크를 통해 문제를 확인해주세요.



📄 문제 개요

KOI 마을에 N개의 빵집이 있습니다. 각 빵집에서 KOI 빵을 사려고 합니다.

• 현재 위치에서 i번째 빵집까지 가는 데 걸리는 시간은 a입니다.
• i번째 빵집에 빵이 들어오는 시간은 b입니다.
• 빵집에 도착하는 시간이 빵이 들어오는 시간보다 늦으면(a > b), 빵이 다 팔려 살 수 없습니다.
• 목표 : 빵을 살 수 있는 빵집 중, 가장 일찍 빵을 구할 수 있는 시간(최소 b)을 구해야 합니다. 모든 빵집에서 빵을 살 수 없다면 -1을 출력합니다.

💡 문제 풀이 시뮬레이션

이 문제는 시간이 흘러가는 것을 복잡하게 시뮬레이션할 필요 없이, 주어진 두 변수(a, b)의 대소 관계만 비교하면 되는 문제입니다.

빵을 사기 위해 체크해야할 필수 조건은 내가 빵집에 도착하는 시간(a)이 빵이 나오는 시간(b)보다 작거나 같아야 한다는 것입니다.

따라서 우리가 할 일은 다음과 같습니다.

1. 모든 빵집을 순서대로 확인하며, a <= b 조건을 만족하는지(빵을 살 수 있는지) 검사합니다.
2. 조건을 만족하는 빵집들 중에서, 빵이 나오는 시간(b)이 가장 작은 값을 찾습니다.
3. 만약 조건을 만족하는 빵집이 단 하나도 없다면 -1을 출력하도록 예외 처리를 해줍니다.

 

💻 코드 구현

n = int(input())

# 시간(b)의 최댓값이 1000이므로, 절대 정답이 될 수 없는 1001을 초기값으로 설정
ans = 1001

# N개의 빵집을 하나씩 확인
for i in range(n):
    a, b = map(int, input().split())

    if a <= b: # 빵집에 도착하는 시간(a)이 빵이 나오는 시간(b)보다 작거나 같을 때만 구매 가능
        if b < ans: # 기존에 찾은 시간보다 더 빨리 나오는 곳을 발견했다면 갱신
            ans = b

if ans == 1001: # ans가 여전히 1001이라면(살 수 있는 빵이 없었다) -1 출력
    print(-1)
else:
    print(ans)

최소값을 구하는 상황에서 ans의 초기값을 무한대(float('inf'))로 잡아도 무방합니다.

하지만 평소 연습할 때 문제 데이터 제한 크기를 확인하여 논리적인 상/하한선을 설정해주면 좋은 공부가 됩니다.



2. 조약돌 (초2)

제목 링크를 통해 문제를 확인해주세요.

📄 문제 개요

좌우 일렬로 놓인 N개의 장소에 조약돌이 있습니다. 다음 두 가지 작업만으로 돌을 치워야 합니다.

1. 인접한 두 장소에서 '동일한 개수'의 조약돌을 가져가기.
2. 한 장소에서 '임의의 개수'의 조약돌을 모두 가져가기.

• 목표: 모든 조약돌을 치우는 데 필요한 최소 작업 횟수를 구해야 합니다. (N <= 2,500)

💡 문제 풀이 시뮬레이션

만약 2번 작업(자기 자리를 모두 치우기)만 쓴다면, 모든 돌을 치우는 데 최대 N번의 작업이 필요합니다.

그렇다면 우리는 이 N번의 작업에서 횟수를 절약할 수 있는 경우를 찾아 빼줘야 합니다.



우리가 이 N번의 전체 횟수를 절약할 수 있는 유일한 방법은 바로 이전 장소와 현재 장소의 돌을 짝지어 동시에 치우는 것(1번 작업)뿐입니다.

하지만 무작정 인접한 돌을 함께 덜어낸다고 해서 무조건 이득이 되는 것은 아닙니다.

연쇄적으로 돌을 지워나가다가 돌이 애매하게 남아버리면, 결국 누군가가 그 자리에 가서 2번 작업을 또 써야 하기 때문입니다.



따라서 우리가 찾아야할 상황은 이전 위치와 엮어서 지워나가다가, 남는 돌 없이 양쪽이 완벽하게 청소되어 횟수가 절약되는 순간입니다.

최대 작업 횟수(N)에서 절약할 수 있는 횟수를 모두 빼면 최소 작업 횟수가 됩니다.



앞선 그림에서 보았듯, 돌을 완벽하게 치워서 횟수를 절약하려면 연쇄 작용이 딱 맞아떨어져야 합니다.

"0번부터 묶어볼까? 아니면 0번은 가만히 두고 1번부터 묶어볼까?" 어느 위치에서 연쇄 작용을 시작할지 모든 경우를 따져봐야 합니다.

이 수많은 경우를 매번 처음부터 다시 계산하면 과정이 너무 복잡해집니다. 따라서 이번에는 동적 계획법(DP)을 활용해보겠습니다.

동적 계획법의 핵심은 "미리 계산해 둔 값을 재활용하자"는 것입니다.

앞에서 힘들게 구했던 답을 뒤에서도 이용하고, 옆에서도 이용하면서 계속 써먹는 방식입니다.

이전까지 확인하면서 얻어낸 가장 많이 절약한 횟수를 DP 테이블(배열)에 적어두고, 이후 단계에서 그 값을 계속 활용할 수 있습니다.

📊 DP 테이블 채우기

예제4 [2, 3, 6, 10, 5]를 통해 DP 테이블 갱신과정을 알아봅시다.

• 초기 상태: DP = [0, 0, 0, 0, 0] (아직 한 번도 절약하지 못함)





1. 0번 위치에서 제거 시작

• 0번 위치의 돌(2개)부터 시작해 인접한 돌들을 묶어서 연쇄적으로 치워나갑니다.
• ①, ②, ③ 과정을 거치며 돌이 계속 남지만, 마지막 ④번 위치에서 남는 돌 없이 딱 0개로 정리됩니다.
• 완벽하게 청소되는 구간을 찾았으므로 1회 절약에 성공했습니다. 이 결과를 4번 인덱스에 기록합니다.

▶ 갱신된 DP 테이블: DP = [0, 0, 0, 0, 1]



2. 0번 위치를 건너뛰고 1번 위치부터 시작

0, 1번 위치를 동시에 치우지 않고 0번 위치만 먼저 정리한 상황입니다.

• ①, ② 과정을 거치다가, ③번 과정에서 남은 돌(7개)이 다음 장소의 돌(5개)보다 많아 함께 처리할 수 없게 됩니다. (추가 절약 실패)
• 절약한 점은 없지만, 앞선 1단계에서 얻어둔 최고 기록(1회 절약)은 날아가지 않고 DP 테이블에 그대로 유지됩니다.

▶ 갱신된 DP 테이블: DP = [0, 0, 0, 0, 1]

3. 이후

• 이후 2번, 3번, 4번 위치를 새로운 기준점으로 잡아 탐색을 계속해도 추가적인 절약은 발생하지 않습니다.
• 결국 DP 테이블의 마지막까지 안전하게 전달된 최대 절약 횟수는 1입니다.

▶ 최소 작업 횟수: 전체 작업 횟수(5) - 최대 절약 횟수(1) = 4번

💻 코드 구현

import sys
input = sys.stdin.readline

n = int(input())
rock = list(map(int, input().split()))

# dp[i]: i번째 장소까지 확인했을 때, 1번 작업을 통해 최대로 절약한 작업 횟수
dp = [0] * n

for i in range(n):
    # 이전까지 모아둔 절약 횟수를 그대로 끌고 옴
    if i > 0:
        dp[i] = max(dp[i], dp[i-1])
        
    x = rock[i]
    # i번째부터 시작해서 이전 돌과 현재 돌을 함께 치워보기
    for j in range(i + 1, n):
        x = rock[j] - x  # 다음 장소의 돌 개수에서 이전 돌 개수만큼 덜어냄
        
        # 돌이 모자라면 이 구간은 완벽히 비울 수 없으므로 탐색 중단
        if x < 0:
            break
            
        # 남는 돌 없이 딱 0이 떨어지는 완벽한 구간을 찾았다면 작업 횟수 1회 절약
        if x == 0:
            if i > 0:
                p = dp[i-1]
            else:
                p = 0
            
            # 기존 절약 기록과 이전 누적 절약 횟수 + 이번 1회 절약 중 더 큰 값으로 갱신
            dp[j] = max(dp[j], p + 1)
            break

# 전체 최악의 작업 횟수(n)에서 최대로 절약한 횟수(dp[-1]를 빼면 최소 작업 횟수
print(n - dp[-1])