2022 KOI(한국정보올림피아드) 중등부 1차 1교시 문제 풀이 (1번~6번)

문제 출처 및 한국정보올림피아드 1차 대회 공식 홈페이지 링크 : https://koi.or.kr/koi/2022/1/

2022년도 한국정보올림피아드 1차 대회

 

2022년 1번 ~ 6번 문제풀이 : https://adanacoding.tistory.com/7

2022 KOI(한국정보올림피아드) 중등부 1차 1교시 문제 풀이 (7번~11번)

---

1. 최대 거리 이진 트리

*전위순회 : 루트노드-왼쪽노드-오른쪽노드 순으로 순회하는 방법

 

전위 순회한 결과가 3, 1, 2, 4가 가능한 경우 :

두 노드 사이의 경로에 포함된 간선의 개수는 2개, 1개, 2개, 3개로 정답은 가장 많은 3개

 

---

2. 달리기

알 수 있는 것부터 정리해 보면,

1. B보다 순위가 낮은 사람은 없다 → B가 5등
2. A는 C보다 순위가 낮다 & D는 A보다 순위가 높다 → C ? D < A < B
3. E의 순위는 B와 A 사이이다 → C ? D < A < E < B

​

그러므로 1, 2등은 C와 D, 3등은 A, 4등은 E, 5등은 B로 정답은 3등인 A

 

---

3. 두 트리 연결하기

A부터 가, 나까지의 거리는 각각 2, 3 / B부터 다, 라, 마까지의 거리는 2, 1, 4이다.

답은 합이 5가 되도록 한 거리가 3인 나와 2인 다

 

---

4. 강아지 모으기

다익스트라 알고리즘의 방식을 활용하면 된다. 다익스트라 알고리즘이란 하나의 정점에서 다른 모든 정점으로 가는 알고리즘인데, 출발 노드를 기준으로 각 노드의 최소 비용을 저장 후, 방문하지 않은 노드 중 가장 비용이 적은 노드를 선택하고 반복하는 것이다.

아래 그림을 보면 먼저 갈 수 있는 모든 노드들을 확인하며 어떤 노드의 비용이 적은 지 탐색을 하고 (회색 마킹), 가장 적은 노드는 방문을 해준다 (회색 마킹 중 가장 작은 값을 빨간색으로 표시 후 해당 노드를 방문했다는 뜻으로 노란색으로 마킹).

(출발하는 섬은 연결이 가장 많이 되어있는 섬으로 했다)

이렇게 되면 연료는 6, 2, 2, 4, 3 만큼 사용했고, 정답은 모두 더한 17

 

---

5. 두 팀

A과 B는 다른 팀으로 고정을 해 총 6명을 2팀으로 나누면 된다.

답은 6C3 = 20, 20

 

---

6. 정육각형 위의 점

7개의 점의 거리를 최대한으로 하면 위 그림과 같다. 가장 적은 길이는 3, 답은 3

추가로 왜 이보다 더 클 수 없냐 하면 비둘기집 원리에 따라 두 점은 6개의 삼각형 안에 들어와 삼각형의 길이인 3보다 클 수 없기 때문이다.

 

---

저도 중등부 대회 나갔던 사람으로 풀이가 확실하게 맞지 않을 수 있습니다!

피드백, 지적, 질문 편하게 해 주세요 :)