KOI 한국정보올림피아드 · 2026 고등부 · 문제 7 / 8 · 난이도 5

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8

간선 게임

정점 6개, 간선 7개의 무방향 그래프가 있고, 두 정점을 S 와 T 라 해요. 나와 상대가 번갈아 간선 하나와 1~7 의 정수 하나를 골라 그 간선에 정수를 배정해요. 이미 정수가 배정된 간선이나 이미 쓴 정수는 다시 고를 수 없고, 내가 먼저 시작해요. 모든 간선에 정수가 배정되면 끝나요. S 에서 T 로 가는 길의 난이도는 그 길 위 간선의 정수 중 가장 큰 값이고, 그래프의 난이도는 모든 길의 난이도 중 가장 작은 값이에요. 나는 난이도를 최소화하고, 상대는 최적으로 행동해 최대화해요. 상대와 겨뤄서 난이도를 이론적으로 가능한 최솟값으로 만드세요.

조작 0회 · 권장 8회 이내정수를 배정한 간선 0/7
·······S2345T1234567간선을 누른 뒤 정수를 누르세요

이전: 등비수열의 합다음: 지연 탐색

출처: 한국정보올림피아드(KOI) 2026 1차 대회 고등부 1교시 · 간선 게임 (https://www.biko.kr/problem/5894) · 비코(biko.kr, 사단법인 한국비버정보교육연합)에서 발췌했으며 허락을 받아 다시 구현해 사용했습니다.