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

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

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

1. 크림빵 (초1)

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

📄 문제 개요

KOI 빵집에서 총 N * K개의 빵을 만들었습니다. 이 빵들을 일렬로 늘어놓고 앞에서부터 K개씩 묶어서 판매하려고 합니다.

• 크림이 있는 빵은 1, 크림이 없는 빵은 0으로 표시됩니다.
• 단, 한 묶음 안에 크림이 없는 빵(0)이 P개 이상 있다면 그 묶음은 불량품으로 간주되어 팔 수 없습니다.

우리는 판매 가능한 빵 묶음의 총 개수를 구해야 합니다.

💡 문제 풀이 시뮬레이션

이 문제를 해결하기 위한 핵심은 일렬로 늘어선 데이터를 일정한 간격(K)으로 정확하게 나누어 검사하는 것입니다.

예를 들어 빵이 3개씩 한 묶음(K=3), 크림 없는 빵이 1개 미만이어야 판매 가능하다고 상상해 봅시다.

주어진 빵의 데이터를 K개씩 끊어서 크림 없는 빵의 개수를 세어보면 판매가능한 빵 묶음 개수를 확인할 수 있습니다.



💻 코드 구현 - K개씩 끊어서 확인하기

# N: 묶음 수, K: 묶음당 빵의 수, P: 불량품 기준 개수
n, k, p = map(int, input().split())
breads = list(map(int, input().split()))

ans = 0

# 0부터 전체 빵 개수(N*K)까지 K칸씩 건너뛰며 묶음의 시작점(i) 설정
for i in range(0, n * k, k):
    nocream = 0  # 현재 묶음의 크림 없는 빵(0) 개수를 셀 변수
    
    # 시작점(i)부터 i+k 직전까지 빵을 하나씩 검사
    for j in range(i, i + k):
        if breads[j] == 0:
            nocream += 1  # 크림이 없으면 개수 증가
            
    # 해당 묶음 안의 불량품이 P개 미만이라면 판매 가능
    if nocream < p:
        ans += 1

print(ans)

전체 빵을 K개씩 끊어 순회하면서 크림없는 빵의 개수를 세고, 불량 여부를 판단하는 것을 중첩 반복의 형태로 표현했습니다.

이번 문제는 빵의 최대 개수(1 <= N <= 50)가 크지 않기 때문에 이 방법으로 충분히 해결 가능합니다.

📊 정답률



2. 대피소 (초2/고1)

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

📄 문제 개요

KOI 마을에 N개의 집이 있습니다. 이 중 K개의 집에 대피소를 설치하려고 합니다.

모든 주민의 안전을 위해, 어떤 집에서든 '가장 가까운 대피소까지의 거리' 중 가장 먼 거리가 최소가 되도록 대피소를 설치해야 합니다.

• 두 집 사이의 거리는 가로 차이와 세로 차이를 합한 값으로 계산합니다.
• 조건을 만족하는 K개의 집을 선택했을 때, 대피소와 가장 멀리 떨어진 집과의 최소 거리를 출력해야 합니다.

💡 문제 풀이 시뮬레이션

이 문제에서 최적의 위치를 단번에 도출해 내는 수학적 공식이나 모델링을 찾으려 한다면, 오히려 출제 의도에서 벗어날 수 있습니다.

집의 개수(N)는 최대 50개이고, 설치할 대피소(r)는 최대 3개입니다.

50개의 집 중에서 3개의 대피소를 고르는 모든 경우의 수는 50C3으로 고작 19,600가지에 불과합니다.

따라서 복잡한 최적화 알고리즘을 구상할 필요 없이, 19,600가지의 대피소 설치 경우의 수를

모두 확인하는 완전 탐색(Brute-Force) 방식으로 접근하는 것이 가장 정확하고 확실한 해결책입니다.



위와 같이 (1, 5), (3, 0), (3, 3), (6, 12), (8, 9) 위치에 총 5개의 집이 있습니다. 이 중 (1, 5), (3, 0) 두 집을 대피소로 선정한 상황입니다.

• (1, 5) 위치의 집 : 대피소로 선정되었기 때문에 가장 가까운 대피소까지의 거리는 0입니다.
• (3, 0) 위치의 집 : 대피소로 선정되었기 때문에 가장 가까운 대피소까지의 거리는 0입니다.
• (3, 3) 위치의 집 : (1, 5) 대피소까지 거리는 4, (3, 0) 대피소까지 거리는 3이므로 가장 가까운 대피소까지의 거리는 3입니다.
• (6, 12) 위치의 집 : (1, 5) 대피소까지 거리는 12, (3, 0) 대피소까지 거리는 15이므로 가장 가까운 대피소까지의 거리는 12입니다.
• (8, 9) 위치의 집 : (1, 5) 대피소까지 거리는 11, (3, 0) 대피소까지 거리는 14이므로 가장 가까운 대피소까지의 거리는 11입니다.

따라서 가장 가까운 대피소까지의 거리가 가장 먼 경우는 (6, 12) 위치의 집의 12가 됩니다.

지금 구한 이 값은 경우의 수 하나의 값이고, 모든 경우의 수에서 계산한 후 가장 작은 값을 구해야 합니다.

풀이과정을 정리해보면 다음과 같습니다.

① 주어진 N개의 집 중 r개를 대피소로 정합니다.

② 각 집과 대피소 사이 가장 가까운 거리(p)를 구한 후, 그 중 가장 큰 값(k)을 선정합니다.

③ 모든 경우에 대해 위 과정을 반복하여 k 중 가장 작은 값(m)을 구합니다.

💻 코드 구현



n, r = map(int, input().split())
arr = []
for i in range(n):
    arr.append(tuple(map(int, input().split())))

n = len(arr)
data = []         # 현재 선택된 대피소들을 담을 리스트
m = float('inf')  # 최종 정답 (가장 작은 값을 찾기 위해 무한대로 초기화)

# 조합을 직접 만들어내는 재귀함수 (start: 탐색 시작 인덱스, depth: 선택한 대피소 개수)
def comb(start, depth):
    global m
    
    # r개의 대피소를 모두 골랐다면
    if depth == r:
        k = 0  # 현재 대피소 조합에서 가장 멀리 떨어진 집의 거리
        
        # 마을의 모든 집(i)에 대해 검사
        for i in arr:
            p = float('inf')  # 현재 집(i)에서 가장 가까운 대피소까지의 거리
            
            # 선택된 대피소(j)들을 하나씩 확인하며 최단 거리 계산
            for j in data:
                p = min(p, abs(i[0]-j[0]) + abs(i[1]-j[1]))
            
            # 모든 집들 중 가장 대피소와 멀리 떨어진 거리(최댓값) 갱신
            k = max(k, p)
            
        # 이번 조합의 최댓값(k)이 기존의 최소 거리(m)보다 작다면 정답 갱신
        m = min(m, k)
        return

    # 대피소 고르기
    for i in range(start, n):
        data.append(arr[i])      # 1. 대피소 선택
        comb(i + 1, depth + 1)   # 2. 다음 대피소 고르러 재귀 호출
        data.pop()               # 3. 탐색 완료 후 빼내고 다른 집 선택

comb(0, 0)
print(m)



1. 알고리즘 문제 풀이 요령

이번 문제 뿐만 아니라 알고리즘을 설계할 때 가장 먼저 확인할 것이 입력 데이터의 크기와 제한시간입니다.

집의 개수(N)의 최대값이 50으로 굉장히 작은데도 불구하고, 문제의 시간제한이 4초로 아주 크게 주어졌습니다.

입력 데이터의 크기와 시간 제한은 이렇게 완전 탐색을 암시하는 힌트가 될 수 있습니다.

알고리즘 설계 방향에 이를 반영하되, 문제에 따라 예외 상황이 있을 수 있기 때문에 올바른 판단을 위해 많은 문제 풀이 경험이 필요하겠습니다.

2. 재귀함수를 활용한 조합 구현

combinations 라이브러리를 활용할 수도 있지만, 재귀함수를 활용해 직접 조합을 구현했습니다.

조합 라이브러리가 구현되어있지 않는 프로그래밍 언어를 사용하거나 라이브러리 사용이 제한적인 상황에서 문제를 잘 풀어내려면

순열/조합과 같은 중요한 개념은 이렇게 직접 구현하는 연습도 해보면 좋겠습니다.

📊 정답률

3. 아이템 획득 (초3)

추가 예정