2023 한국정보올림피아드(KOI) 2차 대회 중등부
한국 정보올림피아드(KOI) 기출 문제 풀이과정을 수록합니다.
1. 스케이트 연습 (초2/중1/고1)
제목 링크를 통해 문제를 확인해주세요.
📄 문제 개요
N개의 체크포인트(중간 지점)가 있는 스케이트 코스가 있습니다.
- 출발점과 도착점에서의 속력은 반드시 0이어야 합니다.
- 각 체크포인트에는 넘어서는 안 되는 속력 제한(V)이 있습니다.
- 속력을 높일 때는 제한 없이 확 높일 수 있지만, 속력을 낮출 때는 직전 지점의 속력에서 딱 1만큼만 낮출 수 있습니다.
- 목표 : 조건을 지키며 코스를 완주할 때, 각 체크포인트에서 낼 수 있는 속력들의 총합의 최댓값을 구해야 합니다.
💡 문제 풀이 시뮬레이션
보통 문제를 풀 때 배열의 처음부터 끝으로 순서대로 탐색하는 것이 일반적입니다.
하지만 이 문제를 앞에서부터 탐색하게 되면 로직이 매우 복잡해집니다.
속력을 낮출 때는 1씩만 낮출 수 있다는 조건 때문에, 현재 위치에서 속력을 마음 편히 올리려면 앞으로 남은 모든 코스의 속력 제한을 미리 내다보고 계산해야 하기 때문입니다. 이런 상황에서는 탐색의 방향을 완전히 뒤집어 도착점부터 역방향으로 탐색해보는 것이 아주 좋은 해결책이 됩니다.
도착점부터 거꾸로 생각하면, 원래의 속력을 최대 1만 낮출 수 있다는 조건은 반대로 속력을 최대 1만 높일 수 있다는 단순한 조건으로 바뀝니다.
도착점의 속력은 무조건 0이기 때문에 도착 지점의 속력 0에서 시작합니다.
각 지점에서의 최대 속력은 ① 현재 지점의 속력 제한(V)과 ② 다음 지점의 속력 + 1 중 더 작은 값으로 단순하게 결정됩니다.
💻 코드 구현
import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
speed = 0 # 현재 위치에서의 최대 속력 (도착점은 0이므로 0부터 시작)
ans = 0 # 낼 수 있는 속력들의 총합
# 배열의 맨 끝(도착점 직전)부터 첫 번째 지점까지 거꾸로 탐색
for i in range(n - 1, -1, -1):
if speed < arr[i]: # 1. 내 속력을 1 높여도 속력 제한(arr[i])보다 작다면?
speed += 1 # 마음 편히 속력을 1 올림
else: # 2. 내 속력을 1 높이면 속력 제한을 넘어가 버린다면?
speed = arr[i] # 해당 지점의 제한 속력에 맞춤
ans += speed # 결정된 속력을 정답에 누적
print(ans)
데이터의 개수 N이 최대 50만 개로 꽤 크지만, 이중 반복문 없이 배열을 거꾸로 한 번만 스캔(시간 복잡도 : O(N))하므로 2초의 시간 제한을 아주 여유롭게 통과합니다.
📊 정답률
100점을 받은 학생 비율이 초등부 50% 정도, 중등부 80% 이상, 고등부 90% 이상이었습니다.
초등부 학생들도 2번 문제치고는 난이도가 평이한 수준, 중/고등부에서는 반드시 맞춰야할 쉬운 문제였습니다.
참고로 풀어볼 만한 문제 링크를 하나 추가했으니, 시간이 나면 풀어보세요.
COCI 6회 "미래를 보는 투자자" 문제 풀이하러가기
2. 호숫가의 개미굴 (초3/중2)
추가 예정
3. 고기 파티 (초4/중3)
추가 예정
4. 지그재그 (중4/고2)
추가 예정