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

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

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

---

[중등부 유형 1 - 사고력] 01번

7의 거듭제곱들의 일의 자리는 7, 9, 3, 1을 반복한다. 이들을 5로 나눈 나머지는 2, 4, 3, 1이다.

2, 4, 3, 1, 2, 4, 3, 1... 쭉 4개가 반복이 되고, n번째 수는 n을 4로 나누었을 때 나머지가 1이면 7^n/5의 나머지는 2, 2면 4, 3이면 3, 0이면 1이라는 것을 알 수 있다 2020/4의 나머지는 0, 1이 된다.

 

[중등부 유형 1 - 사고력] 02번

AA로 이길 확률 1/4 (A로 이길 확률 1/2 * A로 이길 확률 1/2), BAA나 ABA로 이길확률 각각 1/8, BBAA, BABA, ABBA로 이길 확률 각각 1/16이다. 이들을 모두 더하면 1/4 + 2/8 + 3/16 = 11/16

 

[중등부 유형 1 - 사고력] 03번

인접한 9 칸 중 0이 있는 부분을 초록색으로 칠하고, 인접한 칸의 아직 파지 않은 부분이 지뢰 수와 같아 모두 지뢰가 있을 수 있는 경우를 찾아 빨간색으로 칠한다. 다음으로, 지뢰가 있을 수도 있고 없을 수도 있는 부분을 노란색으로 칠한다. 빨간색 블록으로 표시되어 있는 '가'는 확실하게 지뢰가 있으므로, 지우면 안 된다.

 

[중등부 유형 1 - 사고력] 04번

버블정렬을 실행하면 5, 4, 8, 9, 1, 11, 12, 2, 6, 7, 10 15 / 4, 5, 8, 1, 9, 11, 2, 6, 7, 10, 12, 15 / 4, 5, 1, 8, 9, 2, 6, 7, 10, 11, 12, 15로 정렬이 된다. 맨 끝에서 세 번째 자리에는 11이 존재한다.

 

다른 방식으로 풀 수도 있는데 버블정렬에서는 1회전을 수행하고 난 후에는 가장 큰 자료가 맨 뒤로 이동하게 된다. 맨 끝 자료를 제외시키고 다시 회전을 한다면, 회전을 n번 반복하였다면, 전체 배열의 끝에서 n번째 자리에는 배열 중 n번째로 큰 수가 들어온다는 사실을 알 수 있다. 이를 문제에 대입시켜 3번째로 큰 수를 찾아 11이 답이라는 것을 알 수 있다.

 

[중등부 유형 1 - 사고력] 05번

1번 상자만 참이라고 하면, 1번 상자에 금화가 있고, 2번 상자에 금화가 있고, 1번 상자에 금화가 있게 되어 모순이 발생한다. 2번 상자만 참이라고 하면 1번 상자에 금화가 없고, 2번 상자에 금화가 없고, 1번 상자에 금화가 있게 되어 모순이 발생한다. 3번 상자만 참이라고 하면 1번 상자에 금화가 없고, 2번 상자에 금화가 있고, 1번 상자에 금화가 없어 2번 상자에만 금화가 있다는 것을 알 수 있다.

 

[중등부 유형1 - 사고력] 06번

B가 1을 고른다면 A는 2부터 20까지 19개를 고를 수 있고 B가 2를 고른다면 A는 3부터 20까지 18개를 고를 수 있다. A, B는 20가지를 고를 수 있으니 20*20, 모두 400가지 경우의 수로 고를 수 있고 A가 B보다 클 경우의 수는 19+18+...+1개, 190개이다. 190/400, 약분하여 19/40의 확률로 A가 B보다 크게 고를 수 있다.

 

[중등부 유형 1 - 사고력] 07번

남편이 유전적으로 연결된 자식이 9명이기 때문에 유전적으로 연결되지 않은 자식들은 12-9, 3명이라는 것을 알 수 있다. 부인도 똑같이 연결된 자식이 9명이어서 연결되지 않은 자식들은 3명이고, 남편과 부인 둘 다 연결된 자식은 12-(3+3), 6명이다.

 

[중등부 유형1 - 사고력] 08번

그룹을 4명씩 3개로 나눈 후에 한 번씩 차를 타고, 나머지 시간은 걸어간다. 이 시간을 계산해 보면 2시간 36분이 나온다.

 

[중등부 유형 1 - 사고력] 09번

자기 번호와 그 배수인 문들에게 작업을 수행한다면 문 번호의 약수의 개수만큼 문을 열고 닫는 작업을 수행하게 된다. 문 번호가 짝수이면 닫혀있고, 문 번호가 홀수이면 열려있다. 위 선택지들에서 2, 5, 7, 72는 약수의 개수가 짝수개이고 49는 홀수개이다. 이에 따라 49 혼자 방 문이 열려있게 된다.

 

[중등부 유형 1 - 사고력] 10번

n을 4라고 가정하고 k를 2라 가정하여 공을 옮기면 위와 같다.

 

이후 B에 있는 공을 다시 A로 옮기면 다 x, y의 값이 같은 것을 알 수 있다. 

 

좀 더 수학적으로 접근해 보기 위해 컵 B에서 빨간 공을 옮긴 개수를 a, 파란공을 옮긴 갯수를 b라고 하자.

k = a+b, k-a = b, k = a+(k-a), k=k로 a, b에 관계없이 모두가 다 같다는 것을 알 수 있다.

이에 따라 x는 y이다.

 

[중등부 유형 1 - 사고력] 11번

1은 1가지, 2는 2가지, 3은 4가지 방법이 있다. 4는 1+1+1+1, 2+1+1, 1+2+1, 1+1+2, 2+2, 3+1, 1+3으로 7가지 방법이 있고 5는 13가지 방법이 있다. 4는 1과 2와 3의 방법수를 더했고, 5는 2와 3과 4의 방법의 수를 더했다. 8까지 배열로 표현하면 1, 2, 4, 7, 13, 24, 44, 81이고 81가지이다. (dp 국룰문제이다)

 

[중등부 유형 1 - 사고력] 12번

 

길이를 n이라고 하면, n이 1일 때는 1개, 2일 때는 2개, 3개일 때 3개, 4개일 때 5개로 n번째 개수는 (n-1의 타일개수) + (n-2의 타일개수)이다. 수열로 만들면 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 총 89개의 방법이 있다. (이것은 전 문제보다 더 유명한 dp 문제이다)

---

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

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