2025년 정보올림피아드 필기 초등부(11 ~ 15)
2025년도 정보올림피아드 1차대회 필기 초등부 11번부터 15번까지 문제 풀이 입니다.
11번
간단한 수학 문제 입니다. 위 식들은 다음과 같이 나타낼 수 있습니다.
- 341 = n * x + 5 → 336 = n * x
- 508 = n * y + 4 → 504 = n * y
- 579 = n * z + 3 → 576 = n * z
이제 336, 504, 576 의 공약수들의 합을 구하면 됩니다. 세 수의 최대 공약수는 24입니다.
24의 약수는 1, 2, 3, 4, 6, 8, 12, 24 입니다. 여기서 나머지가 5, 4, 3이 나오기 위해서는 5보다는 큰 숫자들만 가능합니다.
따라서 6, 8, 12, 24만 가능하며 이들의 합은 50 입니다.
12번
먼저 한 자리 수의 개수 A를 생각해 보겠습니다. 첫 행과 열의 3까지의 곱은 한 자리 수 입니다.
- 3 * 3 = 9
4는 2까지 가능 합니다. 이것이 양쪽으로 2군데 있습니다.
- 2 + 2 = 4
5부터는 한 자리 수만 가능합니다. 2만 곱해도 10이 되기 때문 입니다. 양쪽에 5개씩 존재 합니다.
- 5 * 2 = 10
따라서 한 자리 수는 총 9 + 4 + 10 = 23 입니다.
다음으로 두 번째 자리의 수 B를 생각해 보겠습니다. 두 자리 수만 계산하기 힘들기 때문에 한 자리, 두 자리수를 모두 계산한 다음 한 자리 수를 빼주는 방식으로 진행 하겠습니다.
먼저 두 자리 수를 나타 낼 수 있는 행과 열을 기준으로 공통의 수는 9까지 입니다. 10 * 10 은 100이 되기 때문에 세 자리수가 되기 때문 입니다.
9 * 9 = 81 로 1부터 9까지의 수들의 숫자를 구하였습니다.
행을 기준으로 이제 10 이후로 생각해 보겠습니다. 10, 11은 곱이 두 자리 수가 되는 경우가 열이 9까지 일 때 가능 합니다.
10 * 9 = 90, 11 * 9 = 99 이기 때문 입니다.
10, 11 행의 각각 9까지 가능하고, 열쪽도 마찬가지이기 때문에 두 배 계산해 줍니다.
9 * 2 * 2 = 36
이런식으로 계속 계산해 주면 19까지 구할 수 있습니다.
12는 8까지 가능합니다.
13, 14는 7까지 가능 합니다.
15, 16은 6까지 가능 합니다.
17, 18, 19 는 5까지 가능 합니다.
12부터 19까지의 개수를 더해주면 8 + 7 * 2 + 6 * 2 + 5 * 3 = 49개 입니다.
양쪽에 있기 때문에 2를 곱해 98개가 됩니다.
그럼 총 두 자리 수는 81 + 36 + 98 - 23 = 192가 됩니다.
23을 뺀 이유는 한자리 숫자들을 빼주어야 하기 때문입니다.
A 는 23, B 는 192 를 구했습니다. C 는 전체에서 A, B를 빼주면 됩니다. 전체는 19 * 19로 361 입니다.
C = 361 - 192 - 23 = 146 입니다.
모든 숫자를 구했으니 A + 2B + 3C를 계산하면 됩니다.
이 계산도 복잡하다면 A + B + C 가 전체 이기 때문에 전체 + B + 2C 이런식으로 계산해도 같은 결과를 얻을 수 있습니다.
답은 23 + 2 * 192 + 3 * 146 = 845 입니다.
13번
모든 칸이 짝지어 질 수 있도록 클릭하면 되는 문제 입니다. 아래 방법 외에 자신만의 정답을 만들어도 됩니다.
14번
간단한 위상 정렬의 문제 입니다. 들오어는 간선이 없는 정점들의 가중치는 1이 됩니다.
정점의 간선들이 연결한 모든 정점의 가중치를 2로 변경 합니다.
가중치 2에서 연결된 모든 정점의 가중치를 3으로 변경 합니다.
마지막으로 3의 가중치를 가진 정점이 연결된 정점의 가중치를 4로 변경 합니다.
15번
루트 부터 시작해서 각 마지막 정점까지의 비용을 계산해보면 어디를 줄여야 할지 쉽게 찾을 수 있습니다.
모든 정점까지 계산해보니 위와 같은 결과를 얻을 수 있습니다. 빨간색으로 표시 되어 있는 간선들의 길이를 조절하면 10을 만들 수 있어 보입니다. 위에서부터 4개의 정점들과 연결된 정점들로 길이를 줄여 나갑니다.
그럼 다음과 같은 결과를 얻을 수 있습니다.
