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

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

1번부터 10번은 아래 링크 확인 바랍니다.

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

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

 

11번

이런 문제는 직접 계산해보면서 규칙을 찾는것이 빠릅니다. 규칙이 보이는지 0에서 10까지 변화를 보겠습니다.

0000000000 → 0000000001 = 1, 1

0000000001 → 0000000010 = 2, 3

0000000010 → 0000000011 = 1, 4

0000000011 → 0000000100 = 3, 7

0000000100 → 0000000101 = 1, 8

0000000101 → 0000000110 = 2, 10

0000000110 → 0000000111 = 1, 11

0000000111 → 0000001000 = 4, 15

0000001000 → 0000001001 = 1, 16

0000001001 → 0000001010 = 2, 18

어렴풋이 규칙이 보입니다. 먼저 0에서 1까지는 1번 바뀝니다. 0에서 2인 10까지는 총 3번 바뀝니다. 0에서 4인 100까지는 7번 바뀝니다. 16인 1000까지는 15번 바뀝니다. 즉 2 ** n 까지 바뀌는 값은 2 ** n - 1번 바뀌는 것을 알 수 있습니다.

그럼 0부터 1000000000 까지는 2 ** 10 - 1 번 바뀌게 됩니다. 우리가 구하려는 값은 1000000000가 아니라 1111111111 입니다. 따라서 1000000000이 되는 횟수 더하기 10000000이 되는 횟수 10000000이 되는 횟수 1000000이 되는 숫자를 모두 더해야 합니다.

(2 ** 10 - 1) + (2 ** 9 - 1) + (2 ** 8 - 1) + …. + (2 ** 2 - 1) + (2 ** 1 - 1) 이 됩니다. 이것은 2의 1승부터 2의 10승까지 등비 수열의 합에다가 10을 뺀 것과 같습니다.

첫째항이 2, 공비가 2인 등비수열에서 10항까지의 합은 다음과 같습니다.

2 * ( 2 ** 10 - 1) / (2 - 1) = 2 * 1023 = 2046

등비수열의 합을 구할지 모른다면 10개니까 2 + 4 + 8 + 16 … + 1024를 직접 해도 됩니다. 그럼 위와 같은 2046을 얻을 수 있습니다. 이 값에 10을 뺀 2036이 정답 입니다.

 

12번

 

처음부터 진행해서 29/67을 찾는 것은 힘듭니다. 거꾸로 찾아가야 쉽게 찾을 수 있습니다. 왼쪽으로 갈 때에는 앞의 숫자가 작고, 오른쪽으로 갈 때에는 뒤의 숫자가 작은 것을 이용해서 문제를 해결할 수 있습니다.

• 29 / 67은 앞의 숫자가 작기 때문에 왼쪽인 L로 갈 수 있습니다. p와 q의 값을 알아보면 29 / (29 + 38)이라는 숫자를 찾을 수 있습니다. 그럼 이전 숫자는 29 / 38 입니다. ( L, 29 / 38 )
• 29 / 38 역시 L로 이동합니다. 그리고 29 / (29 + 9) 로 나타낼 수 있습니다. (L, 29 / 9)
• 29 / 9는 앞 숫자가 더 크기 때문에 이번에는 R로 이동 합니다. (9 + 20) / 9 입니다.(R, 20 / 9)
• 20 / 9 역시 R 입니다. p, q를 나누면 (9 + 11) / 9 입니다. (R, 11 / 9)
• 11 / 9 도 R 입니다. (9 + 2) / 9 입니다. (R, 2 / 9)
• 2 / 9는 L 입니다. 2 / (2 + 7) 입니다. (L, 2 / 7)
• 2 / 7 은 L 입니다. 2 / ( 2 + 5) 입니다. (L, 2 / 5)
• 2 / 5 로 가는 경로는 위 그림에 표시되어 있습니다. RLLL로 이동합니다.

모든 경로를 알았습니다. 위에서부터 거꾸로 찾은 것이기 때문에 거꾸로 경로를 더해주면 답을 찾을 수 있습니다.

RLLLLLRRRLL

 

13번

 

 

교차하는 간선이 없도록 하기 위해서는 바깥의 정점을 안으로 넣어주면 됩니다.

위와 같이 두 정점을 안으로 넣어주면 문제가 해결 됩니다.

14번

거리가 먼 곳에 큰 원판을 넣어가면서 거리를 조절해주면 쉽게 문제를 해결할 수 있습니다.

 

15번

숫자가 큰 보물이 무엇인지 확인합니다. 59, 55, 53, 55, 51이 큽니다. 따라서 가장 왼쪽에 있는 뚜껑을 제외하고 나머지 뚜껑을 이동하면 됩니다.

맨 앞에 있는 뚜껑은 오른쪽에 있는 큰 숫자들로 이동할 수 없습니다. 하지만 왼쪽으로 이동한다면 32보다 7 큰 39로 이동이 가능합니다. 맨 앞의 뚜껑을 39로 이동하면 합이 306이 됩니다.