2024. 2. 17. 00:20ㆍ💻 Dev Log/한국정보올림피아드(KOI) 문제 풀이
문제 및 한국정보올림피아드 1차 대회 공식 홈페이지 링크 : https://koi.or.kr/koi/2023/1/
2023년도 한국정보올림피아드 1차 대회
대회 응시자를 위해 공지되었던 안내사항은 응시자 안내사항 페이지에서 확인해 주세요.
koi.or.kr
1. 양팔 저울
정답 : 12kg
2kg + 5kg + (물 1kg) = 8kg / 2kg + (물 6kg) = 8kg / 2kg + (물 11kg) = 5kg + 8kg
2. 봉투
정답 : 7
지폐들 중 가장 적은 금액이 3000원 이므로, 모든 봉투에 6000원 미만의 금액이 들어가야 한다.
즉 모든 봉투에 천 원짜리가 5개 이하로 들어가 있어야 한다.
9장이 들어있는 봉투에서 4개를 빼고, 8장이 들어있는 봉투에서 3개를 빼어 2개의 봉투를 추가하면, 조건을 만족한다.
기존 봉투 5장에 추가한 봉투 2장으로, 답은 7
3. ABAB
정답 : 6
b / a b / a b / b a / a b / a로, 총 6조각으로 나눌 수 있다.
이때 먼저 고려하면 좋을 부분은, bbaa와 같이 같은 문자가 연속된 부분이다.
4. 교수와 학생
정답 : 60가지
교수가 앉을 수 있는 자리만을 고려하면 총 10가지이다.
(모든 경우의 수 보기)
_ ㅁ _ ㅁ _ ㅁ _ _ _
_ ㅁ _ ㅁ _ _ ㅁ _ _
_ ㅁ _ ㅁ _ _ _ ㅁ _
_ ㅁ _ _ ㅁ _ ㅁ _ _
_ ㅁ _ _ ㅁ _ _ ㅁ _
_ ㅁ _ _ _ ㅁ _ ㅁ _
_ _ ㅁ _ ㅁ _ ㅁ _ _
_ _ ㅁ _ ㅁ _ _ ㅁ _
_ _ ㅁ _ _ ㅁ _ ㅁ _
_ _ _ ㅁ _ ㅁ _ ㅁ _
이때 3개의 의자의 교수들이 앉을 수 있는 방법은 총 6가지이다. (3*2*1)
따라서 교수가 앉을 수 있는 자리에 교수들이 앉을 수 있는 경우의 수는 10*6, 60가지이다.
5. 가전제품 교체
정답 : 8
현재 꽂혀 있는 가전제품 중 앞으로 쓰이지 않거나, 최대한 늦게 쓰일 가전제품을 우선적으로 교체하면서 손으로 구해보면, 답을 구할 수 있다.
교체 방법 예시
1 > 8
2 > 5 > 6
3 > 7 > 3
4 > 3 > 5 > 2
6. 배수
정답 : 801
먼저 3의 배수 혹은 4의 배수인 자연수의 개수는 (3의 배수 개수)+(4의 배수 개수)-(12의 배수 개수)로 구할 수 있다.
(12의 배수의 경우 3의 배수, 4의 배수에서 2번 더해지기 때문에 한번 빼주어야 한다.)
(3의 배수 갯수)+(4의 배수 개수)-(12의 배수 개수) = 667+500-166 = 1001
5의 배수가 아닌 수는 각각의 5의 곱인 (15의 배수 갯수)+(20의 배수 개수)-(60의 배수 개수)로 구할 수 있다.
(15의 배수 갯수)+(20의 배수 개수)-(60의 배수 개수) = 133+100-33 = 200
1001-200 = 801.
7. 근무 계획
정답 : 211
첫날에 30, 45, 둘째날에 35, 25, 세 번째 날에 29, 16, 네 번째 날에 20, 16의 이익의 작업을 수행하면 된다.
(작업이 p를 기준으로 보기 쉽게 정렬이 되어 있다. 착한 KOI)
8. 점 배치
정답 : 1.0
아래 그림처럼 점을 배치 하면 된다.
(부연 설명을 하자면, 삼각형의 세 꼭짓점에 3개의 점을 놓고, 두 변의 중점에 점을 두는 것)
삼각형의 한 변이 2.0의 길이 이므로 X는 1 이하이다.
9. 이상한 섬
정답 : B 건달, C 신사
C가 건달인 경우 먼저 생각해보자. C가 건달이라면, B는 현재 진실을 말하고 있었을 것이다. 이에 따라, A는 자신이 건달이라고 말한 것이 진실이 된다. 자신이 건달이라고 말을 하는 것은 건달인 경우에도 신사인 경우에도 모순이 발생한다.
C가 신사인 경우에는, B가 거짓을 말하는 것이 된다. 이에 따라 A는 자신이 건달이라고 말하지 않았다는 것을 알 수 있다. 그래서 A는 신사, B는 건달, C는 신사인 것을 알 수 있다.
10. 분수 트리
정답 : RLLLRRRLL
만약에 p/q에서 p가 더 크다면 (p-q)/q, q가 더 크다면 p/(q-p)의 방법으로 1/1이 되도록 만들 수 있다.
이 방법으로 경로를 만들면,
(1/1) > (2/1) > (2/3) > (2/5) > (2/7) > (2/9) > (11/9) > (20/9) > (29/9) > (29/38) > (29/67)이다.
이러한 경로에서 이전 값에서 p가 더 커졌다면 R로 이동하고, q가 더 커졌다면 L로 이동했다는 것을 알 수 있다.
이를 바탕으로 경로를 만들면 RLLLLRRRLL이다.
11. 트리 위의 모임
정답 : 945
제일 간단한 방법은 정점을 기준으로 각각 a, b, c에 대해 노가다로 값을 구하는 것이다.
이 방법 외의 방법으로는 간선을 기준으로 생각하는 것이다. 만약에 해당 간선을 기준으로 양 옆에 모두 노드가 있는 경우, 최단 거리를 구하기 위해 해당 간선을 통하여 이동한다.
예시로 위 그림을 보자. 색칠되어 있는 간선을 기준으로 왼쪽에 6개, 오른쪽에 6개의 정점이 있다.
전체의 그래프에서는 12C3 개의 정점이 선택될 수 있다. 여기에 왼쪽에 모두 쏠리는 경우인 6C3과 오른쪽에 모두 쏠리는 경우인 6C3을 빼면 해당 간선을 220-20-20 = 180, 180번 사용한다는 것을 알 수 있다.
이와 같은 방법으로 모든 간선에 대해 계산을 하면 (12C3)*11 - (11C3)*6 - (10C3)*3 - (9C3) - (6C3)*2 - (3C3) - (2C3)*6 - (1C3)*6 = 220*11 - 165*6 - 120*3 - 84 - 20*2 - 1 = 945. (2C3과 1C3은 계산 X)
12. 쪽지 시험
정답 : 2790
교란순열(완전순열)을 활용하는 문제이다. 청강생이 자신의 시험지를 채점하는지, 채점하지 않는지를 기준으로 생각해야 한다. (교란순열이란? 원래 위치에 있는 원소가 하나도 없는 수열)
먼저 청강생 모두가 자신의 시험지를 채점한다면, 학생 4명이 자신의 것 외의 시험지를 채점하면 된다.
이는 D4 = 9.
다음으로 청강생 모두가 자신의 시험지를 채점하지 않는다면, 학생 7명이 자신의 것 외의 시험지를 채점하면 된다.
이는 D7 = 1854.
청강생 한 명이 자신의 시험지를 채점하지 않는다면, 학생 5명이 자신의 것 외의 시험지를 채점하면 된다.
이는 D5 = 44. 하지만 자신의 것을 채점하지 않는 청강생이 청강생 중 누가 될지 모르기 때문에 3명의 경우를 모두 생각해야 한다. 44*3 = 132.
청강생 한 명만이 자신의 시험지를 채점한다면, 학생 6명이 자신의 것 외의 시험지를 채점하면 된다.
이는 D6 = 265. 하지만 자신의 것을 채점하는 청강생이 청강생 중 누가 될지 모르기 때문에 3명의 경우를 모두 생각해야 한다. 265*3 = 795.
이들을 모두 더하면 9+1854+132+795 = 2790.
저도 중등부 대회 나갔던 사람으로 풀이가 확실하게 맞지 않을 수 있습니다!
피드백, 지적, 질문 편하게 해 주세요 :)
'💻 Dev Log > 한국정보올림피아드(KOI) 문제 풀이' 카테고리의 다른 글
| 2023 정보올림피아드 중등부 1차 후기 (0) | 2023.05.28 |
|---|---|
| 2020 KOI(한국정보올림피아드) 중등부 1차 1교시 문제풀이 (1번~12번) (0) | 2023.04.23 |
| 2019 KOI(한국정보올림피아드) 중등부 1차 1교시 문제풀이 (1번~12번) (0) | 2023.03.19 |
| 2022 KOI(한국정보올림피아드) 중등부 1차 1교시 문제풀이 (13번~20번) (0) | 2023.02.26 |
| 2021 KOI(한국정보올림피아드) 중등부 1차 1교시 문제 풀이 (1번~12번) (4) | 2023.01.23 |