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

2019년 정보올림피아드 필기 초등부 6번부터 10번까지 문제 풀이 입니다.

1번부터 5번까지는 아래 링크 확인 바랍니다.

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

2019년 정보올림피아드 필기 초등부(1~5)

6번

이 문제는 시뮬레이션을 직접하여 첫 번째 개미가 떨어진 시간과 마지막 개미가 떨어진 시간의 차이를 구해야 합니다. 먼저 첫 번째 개미가 떨어질 때까지 시뮬레이션 해보겠습니다. 먼저 시작 시간입니다.

2초 후 첫 번째 개미와 두 번째 개미가 만나 반대 방향으로 가기 시작합니다.

0.5 초 후 4번째 개미와 5번째 개미가 만나 반대 방향으로 가기 시작 합니다. 지금까지 2.5초가 지났습니다.

1.5초 후에 첫 번째 개미가 자의 시작위치에 도달하고, 1초가 지난 후 떨어지게 됩니다. 즉 2.5초 후에 첫 번째 개미가 떨어지게 됩니다. 여기까지 5초가 걸립니다. 5초일 때 첫 번째 개미가 떨어진 것입니다.

2초 후 2번 개미와 3번 개미가 만나게 되고, 4번째 개미는 끝에 도달 합니다. 그리고 1초 후 밑으로 떨어지게 됩니다. 3초가 지난 것이고, 전체로는 8초가 지났을 때 이와 같은 모양이 됩니다.

6초 후에 1번 개미와 2번 개미가 만나게 됩니다. 전체 14초 후 입니다.

2초 뒤 3번 개미가 끝에 도달하고, 1초 후에 떨어집니다. 전체 17초 후 입니다.

11초 뒤 1번 개미가 자의 끝에 도달하고 1초 뒤 떨어집니다. 즉 1번 개미는 12초 후에 떨어집니다. 전체 29초 지났습니다.

1초 뒤 마지막 개미가 자의 끝에 도달하고, 1초 뒤에 떨어집니다. 전체 31초후에 전체 개미가 떨어지게 됩니다.

첫 번째 개미는 5초에 바닥에 떨어졌고, 마지막 개미는 31초에 바닥에 떨어졌습니다. 따라서 31 - 5로 차이는 26초가 됩니다.

 

7번

이 문제 역시 시뮬레이션을 통해 알아보겠습니다. 먼저 시작 시각 0초일 때의 모습입니다.

3초 뒤 첫 번째 멈춤이 발생합니다.

3초가 되었을 때 화살표가 살아있는 두마리의 개미를 제외하면 모든 개미가 멈춰 있습니다. 2초가 지난 5초가 되었을 때 모든 개미가 멈추게 됩니다.

위와 같은 모습이 되고 정답은 5가 됩니다.

 

8번

9글자의 회문을 만드는 문제 입니다. 어렵게 느껴질 수 있으나 결국은 경우의 수를 구하는 문제 입니다. 총 9자의 회문을 만드는 것이 아니라 9의 절반인 5자의 경우의 수를 만들어 주면 됩니다. 그리고 앞의 4자리를 뒤에 회문이 되도록 이어 붙이면 9자의 회문이 되는 것입니다.

위와 같이 5글자의 경우의 수를 구합니다. 그리고 A, B, C, D를 뒤에 반대로 이어 붙이면 회문이 됩니다.

알파벳 a, b, c 3개의 경우가 있으니 3 ** 5인 243이 정답이 됩니다.

9번

재귀를 직접 실행해 보는 문제입니다. 13에서 0이 될 때까지 5번의 연산이 필요하다는 것을 알 수 있습니다. 40에서 13까지 몇 번만에 만들 수 있는지 확인한 뒤 5를 더하면 문제가 해결 됩니다.

먼저 40은 4를 빼면 됩니다.

40 - 4 = 36

36에서 3씩 빼면 3번 실행한 후 27이 됩니다.

36 - 3 - 3 - 3 = 27

지금까지 4번 빼기 연산을 실행 했습니다. 27에서는 4번 2를 빼면 19가 됩니다. 그럼 총 8번의 빼기 연산을 실행한 것입니다.

27 - 2 - 2 - 2 - 2 = 19

19에서 13까지는 6번 1을 빼주면 됩니다.

19 - 1 - 1 - 1 - 1 - 1 - 1 = 13

이제 13에서 0이 될 때까지 5번을 더 빼기 연산을 하면 0이 됩니다. 19가 될 때까지 8번, 13까지 6번, 0까지 5번을 모두 더하면 19번만에 0을 만들 수 있습니다.

10번

벨이 울리면 어린 토끼는 어른 토끼가 되고, 어른 토끼는 어린 토끼를 낳습니다. 결국 어린 토끼 + 어른 토끼가 어른 토끼의 수가 되고, 어른 토끼의 수는 어린 토끼의 수가 됩니다. 이것은 피보나치 수열의 형태임을 알 수 있습니다.

벨을 울린 횟수 어린 토끼 어른 토끼 토끼의 합계

0	1		1
1	0	1	1
2	1	1	2
3	1	2	3
4	2	3	5
5	3	5	8
6	5	8	13
7	8	13	21
8	13	21	34
9	21	34	55

벨을 9번 울렸을 때 전체 토끼의 수는 55가 됩니다. 피보나치 수열을 알고 있다면 쉽게 풀 수 있습니다.