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

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

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

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

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

11번

중심 노드의 진출 차수가 n - 1임이 보장되어 있습니다. 따라서 중심을 찾기 위해서 n - 1번 함수를 호출하면 무조건 중심 노드를 찾을 수 있습니다.

최악의 경우 일렬로 늘어선 트리를 생각할 수 있고, 마지막 트리 노드에서 중심을 찾으려면 n - 1번 거슬러 올라가야 중심노드를 찾을 수 있습니다.

 

12번

오른쪽이나 아래로만 이동 가능하기 때문에 갈 수 있는 경로는 제한적 입니다. 제한적이기 때문에 경로의 개수를 세기는 더 쉬워집니다.

갈 수 없는 경로를 제외하면 아래와 같은 경로만 신경쓰면 됩니다.

왼쪽 상단에 두 점 모두 지나는 방법은 없습니다. 한 점을 지나는 경로를 모두 찾습니다. 모두 찾아보면 총 5개의 경로를 찾을 수 있습니다.

각각의 색깔을 따라가면 5개임을 확인할 수 있습니다. 오른쪽 하단에서 하나 이상의 경로를 찾아보겠습니다. 위와 같은 형태로 경로를 찾으면 총 10개의 경로를 찾을 수 있습니다. 위쪽 5개와 아래쪽 10개를 곱하면 총 50개의 경로를 찾을 수 있습니다.

하지만 아직 끝이 아닙니다. 왼쪽 상단에 점을 하나도 지나지 않아도 아래쪽 하단에서 두 점을 지나는 방법이 있기 때문 입니다.

파란색 선을 지나서 아래쪽 빨간점 두개를 모두 지나는 경로도 고려해 주어야 합니다. 상단에서 점을 지나지 않고 내려오는 경로는 한가지 밖에 없습니다. 그리고 하단에서 두 점을 모두 지나는 경로는 3가지가 있습니다.

따라서 모든 경로는 위에서 구한 50개와 밑에서 구한 3개를 합한 53개가 됩니다.

 

13번

1개의 선물을 사는 것과, 여러개의 선물을 구입하는것 중 어느것이 이득인지 계산해 봐야 합니다.

3개 구입시 400원 이기 때문에 400 / 3 으로 약 133원 정도 되는 것을 알 수 있습니다.

5개 구입시 700원 이므로 700 / 5 로 140원이라는 것을 알 수 있습니다.

따라서 3개가 들어있는 400원짜리 상자를 구매하는 것이 가장 큰 이득이고, 5개가 들어있는 상자를 사는 것이 중간이고, 1개씩 구입하는 것이 가장 비싸게 구입하는 것입니다.

3개가 들어있는 상자 3개와 1개가 들어있는 상자 1개를 구매하면 총 10개를 구매할 수 있습니다.

400 * 3 + 175 = 1375원

 

14번

하노이의 탑을 이해하면 문제를 쉽게 해결할 수 있습니다. 까다로운 점은 하노이의 탑 문제와는 약간 다르게 1번은 2번으로, 2번은 3번으로, 3번은 1번 막대로만 이동한다는 제약이 있습니다. 이는 조금 귀찮은 부분이지만 어려운 부분은 아닙니다. 따라서 몇 번 되돌리며 이동을 잘 시키면 아래와 같은 결론을 얻을 수 있습니다.

 

15번

초등부 16번과 같은 문제 입니다. 아래 링크를 통해 16번 확인 바랍니다.

https://davincicoding.tistory.com/129#16%EB%B2%88

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