2021년 정보올림피아드 필기 중등부(6 ~ 10)

2021년도 정보올림피아드 1차대회 필기 중등부 6번부터 10번까지 문제 풀이 입니다.

이전 문제는 아래 링크 확인 바랍니다.

2024.04.13 - [알고리즘 설명/정보올림피아드 필기] - 2021년 정보올림피아드 필기 중등부(1 ~ 5)

 

6번

초등부 9번과 같습니다. 아래 링크에서 초등부 9번 확인 바랍니다.

https://davincicoding.tistory.com/127#9%EB%B2%88

2021년 정보올림피아드 필기 초등부(6 ~ 10)

 

 

7번

 

루트 노드에서 시작해서 어느 잎 노드에 도달하더라도 그 경로의 가중치의 합이 똑같이 되도록 만들어야 하는 문제 입니다. 끝에서부터 하나 하나 맞춰주면 문제를 해결할 수 있습니다.

잎 노드부터 생각해 보겠습니다.

맨 왼쪽의 경우 왼쪽은 4, 오른쪽은 6으로 2가 차이 납니다. 따라서 4에다가 2를 더해주어 6으로 맞춰 줍니다.

세 번째 1은 네 번째 9와 맞추기 위해 8을 더해줍니다.

다섯 번째 2에 2를 더하고, 8번째 6에 2를 더해 8을 맞춰 줍니다. 그럼 지금까지 증가한 가중치는 2 + 8 + 2 + 2로 14가 됩니다.

 

이제 잎 노드의 한 단계 상단인 노드를 확인해 보겠습니다. 왼쪽은 12 + 6으로 18의 거리를 가지고 있습니다. 오른쪽은 6 + 9로 15를 가지고 있습니다. 3이 차이나기 떄문에 3을 더해주어야 하는데 아래쪽 9에 더하려면 두 군데를 더해야 합니다. 그것보다는 상단 노드를 더하는 것이 효율적이기 때문에 6에다가 3을 더해 줍니다.

오른쪽 노드들을 확인해 보면 세 번째 가지쪽은 9 + 4로 13이고 마지막 가지쪽은 1 + 8로 9 입니다. 여기도 오른쪽을 13이랑 맞추기 위해 1에다가 4를 더합니다.

root 노드를 확인해보니 가중치 합이 왼쪽은 18 + 14로 32가 됩니다. 오른쪽은 7 + 13으로 20입니다. 32를 맞추기 위해 7에다가 12를 더해주면 됩니다.

이제 지금까지 더해준 가중치의 합을 구하면 그것이 최종 가중치에다가 원래 가중치를 빼준것과 같습니다. 따라서 지금까지 더한 모든 값을 확인해보면 다음과 같습니다.

2 + 8 + 2 + 2 + 3 + 4 + 12 = 33

따라서 정답은 33 입니다.

 

8번

초등부 10번과 같습니다. 아래 링크에서 10번 확인 바랍니다.

https://davincicoding.tistory.com/127#10%EB%B2%88

2021년 정보올림피아드 필기 초등부(6 ~ 10)

 

9번

마지막에 남은 모든 돌을 가져가는 사람이 이깁니다. 그럼 A의 차례에 하나씩 두 무더기가 남으면 무조건 지게 됩니다. A가 한 무더기의 하나를 가져가면 B가 나머지 하나의 무더기에서 돌을 가져가고 결국 B가 승리하는 것입니다.

세 개의 무더기에 돌이 하나씩 남았다고 생각하면 A가 한 무더기를 가져가면 B가 한 무더기를 가져가고, 다시 A가 마지막 한 무더기를 가져가 A가 무조건 이깁니다. 따라서 A는 세 개의 무더기에 돌 하나씩 남길 수 있으면 이기게 됩니다.

A가 세 무더기를 만들기 위해서 3개중 2개를 가져가서 한 개만 남겨두면(파란색을 A가 가져간다면), B는 2개 있는 곳을 다 가져갑니다.(초록색을 B가 가져가면) 그럼 위와 같은 형태를 만들 수 없습니다. 결국 A가 지게 됩니다.

A가 3개중 하나를 가져가면 B는 한개짜리를 가져갑니다. 그럼 결국 2개, 2개가 남게 됩니다. 두 개, 두 개가 남으면 A가 하나 가져가면 B는 나머지 한 무더기중 하나를 가져가 1개, 1개가 남아 A가 지게 됩니다.

A가 돌 하나씩 있는 세 무더기를 만들 수 없기 때문에 무조건 B가 이기게 됩니다.

 

10번

나은이는 두 수의 합을 알고 있고, 다래는 두 수의 곱을 알고 있습니다. 대화를 들어보면 나은이는 두 수가 처음엔 몰랐는데 이젠 알겠다고 합니다. 그 말은 다래의 말을 통해 두 수를 유추할 수 있다는 뜻이 됩니다.

먼저 나은이도 처음에는 두 수의 합을 듣고 두 수를 모른다고 했습니다. 만약 두 수의 합이 2라면 나은이는 두 수가 (1, 1)이라는 것을 바로 알 수 있습니다. 두 수의 합이 3이라면 두 수는 (1, 2)임을 알 수 있습니다.

4는 (1, 3)인지, (2, 2)인지 알 수 없습니다. 5 역시 (1, 4), (2, 3)로 답을 알 수 없습니다. 6은 (3, 3), (2, 4)로 알 수 없습니다.

7이 되기 위해서는 (3, 4)만 가능하기 때문에 답을 알 수 있습니다. 8 역시 (4, 4)로 답을 알 수 있습니다.

이제 나은이가 알게된 숫자가 4, 5, 6 중 하나라는 것을 알 수 있습니다.

다음으로 다래의 경우를 생각해 보겠습니다. 다래는 두 수의 곱을 알고 있고 두 수를 유추할 수 없습니다. 곱을 유추할 수 없는 경우는 4일 경우 입니다. 4는 (1, 4)일수도 있고, (2, 2)일수도 있기 때문 입니다. 나머지는 두 수의 곱으로 바로 유추할 수 있습니다. 아래는 곱으로 유추할 수 있는 두 수 입니다.

1	2	3	4	6	8	9	16
(1, 1)	(1, 2)	(1, 3)	(1, 4), (2, 2)	(2, 3)	(2, 4)	(3, 3)	(4, 4)

다래의 말을 통해 나은이는 다래가 알고 있는 수가 4라는 것을 알게된 것입니다. (1, 4), (2, 2) 중 하나이기 때문에 나은이는 바로 알 수 있던 것 입니다.

마지막으로 나은이와 다래가 들은 수가 다르다는 것을 통해 a + b는 5이고, a * b 는 4라는 것을 알 수 있습니다. 즉 a는 1이고, b는 4라는 뜻입니다. 두 수의 제곱은 1 ^ 2 + 4 ^ 2으로 1 + 16 = 17이 됩니다.