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

2021년 정보올림피아드 1차대회 초등부 16번부터 20번까지 문제 풀이 입니다.

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

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

2024.03.31 - [알고리즘 설명] - 2021년 정보올림피아드 필기 초등부(11 ~ 15)

 

16번

A, B, C, D, E가 모두 포함된 가장 짧은 깃발 위치를 찾는 것입니다. 첫 번째 문제는 4번을 포함한 1부터 5번까지를 선택하면 A, B, C, D, E를 포함하면서 가장 짧은 구간이 됩니다.

11번을 포함한 A부터 E까지 모두 포함된 가장 짧은 구간은 3번부터 11번 구간 입니다.

 

3번 문제는 15번째부터, 20번까지 선택하면 됩니다.

4번 문제는 3번부터 9번을 선택하면 됩니다.

5번 문제는 13번부터 19번까지 선택하면 됩니다.

A부터 E까지 확장해 나가며 없는 항목이 들어오는 부분을 찾으면 쉽게 해결할 수 있습니다.

 

17번

편도로 이동할 경우에는 최대한 무거운 두 사람이 이동하는 것이 사용료를 줄일 수 있습니다. 하지만 왔다, 갔다를 반복해야 하기 때문에 돌아올 때 최대한 가벼운 사람이 이동하는 것이 사용료를 줄일 수 있습니다. 따라서 미리 가벼운 사람을 반대편에 가져다 놓고 가장 무거운 사람 두 사람을 이동시킨 다음 가벼운 사람이 돌아오는 방법으로 사용료를 줄일 수 있습니다.

1. (3, 7) 오른쪽으로 이동
2. (7) 왼쪽으로 이동
3. (12, 15) 오른쪽으로 이동
4. (3) 왼쪽으로 이동
5. (3, 9) 오른쪽으로 이동
6. (3) 왼쪽으로 이동
7. (3, 8) 오른쪽으로 이동
8. (3) 왼쪽으로 이동
9. (3, 7) 오른쪽으로 이동

이렇게 하면 총 62의 사용료로 모두 이동이 가능합니다. 62가 된다면 위 방법이 아닌 다른 방법으로 해도 문제를 해결할 수 있습니다. 핵심은 무거운 두사람을 한꺼번에 옮기기와 가벼운 사람으로 최대한 돌아오도록 해야 하는 것입니다.

18번

아직 승, 패가 하나씩 밖에 비교가 되지 않기 때문에 1일차에는 모두가 2등이 될 수 있습니다.

1, 2, 3, 4, 5, 6, 7, 8

2등이 되기 위해서는 자신보다 팔씨름을 잘하는 친구가 1명보다 많으면 안됩니다. 2번은 자신보다 팔씨름을 잘하는 친구가 3, 4번이 있습니다. 이미 자신보다 팔씨름을 잘하는 친구가 2명이니 2등이 될 수 없습니다.

그런 2번이 7번을 이길 수 있기 때문에 7번도 2등이 될 수 없습니다. 그리고 8번 역시 3번, 5번이 이길 수 있으므로 2등이 될 수 없습니다.

1, 3, 4, 5, 6

관계가 추가 되면서 2등이 될 수 없는 친구들이 보입니다. 1번을 3번, 4번이 이길 수 있기 때문에 1번은 2등이 될 수 없습니다. 4번은 모두 이길 수 있습니다. 4번에서 시작해서 이길 수 있는 라인을 따라가면 연결 안된 친구가 없습니다. 즉 팔씨름을 제일 잘한다는 소리이고, 1등이기 때문에 2등이 될 수 없습니다. 6번은 3번, 4번이 이길 수 있기 때문에 2등이 될 수 없습니다. 따라서 3, 5번이 2등을 할 수 있습니다.

3, 5

5번을 이길 수 있는 친구가 3번이 추가 되었습니다. 따라서 5번은 더이상 2등을 할 수 없습니다. 남은 친구는 3번만 남았습니다. 따라서 2등 친구는 3번 입니다

3

 

19번

상대방이 마지막에 못가져가게 하기 위해서는 상대방 차례에 아무것도 없거나, 1개가 남아 있어야 합니다. 이렇게 0개나 1개가 남게 하려면 그 전에는 6개가 남아 있어야 합니다. 상대방이 6개에서 2개를 가져가면 남은 4개 중 3개나 4개를 가져와 더이상 못가져가게 합니다. 3개를 가져가면 나는 2개를 가저와 1개를 남겨줍니다. 마지막으로 4개를 가져가면 나는 2개를 가져와 아무것도 못가져가게 합니다.

이렇게 6의 배수로 남겨두면 쉽게 이길 수 있습니다. 문제는 6의 배수를 가져가면 상대방이 3개를 가져가는 것이 문제 입니다. 왜냐하면 내 차례에 3개를 가져갈 수 없기 때문 입니다. 이런 경우 2개나 4개를 가져와 내가 6의 배수를 맞추기 쉽게 조절해 주면 됩니다.

 

20번

첫 번째 대결은 최대한 많이 이기고, 두 번째 대결은 최대한 많이 지면 되는 것입니다. 첫 번째는 가위로 영희의 보를 다 이기게 합니다. 나머지 승리할 수 있는 것은 다 승리하고, 나머지 하나는 비기게 합니다. 두 번째는 최대한 비기거나 져서 승수를 낮춰 줍니다.

아래와 같이 배치하거나 승리 횟수를 맞게 하면 정답을 맞을 수 있습니다.