2019년 정보올림피아드 필기 초등부(2-4~2-8)

2019년 정보올림피아드 1차 대회 초등부 2-4번부터 2-8번까지 문제 풀이 입니다. 이전 문제 풀이는 아래 링크 확인 바랍니다.

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

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

2024.03.16 - [알고리즘 설명] - 2019년 정보올림피아드 필기 초등부(11~2 - 3)

2-4번

모든 수를 다 곱해봐야 할 것 같지만 그렇지 않습니다. 문제에서 첫 배열은 오름차순, 두 번째 배열은 내림차순으로 되어 있다고 했습니다. 첫 번째 끼리 두 수를 곱해서 504보다 작으면 첫 배열의 위치를 바꿔 숫자를 커지게 만들고, 504보다 크면 두 번째 배열의 위치를 바꿔 숫자를 작게 만들 수 있습니다.

이런 알고리즘 기법을 투 포인터라고 합니다. 각 배열에 포인터를 두고 어느 것을 이동할 지 정해 결과를 얻습니다.

가장 첫 번째의 숫자들의 곱은 504입니다. 첫 번째 504를 찾았습니다. 그럼 다음으로 넘어가 보겠습니다.

3 * 126은 378 입니다. 숫자가 504보다 작기 때문에 숫자를 크게 만들어 주기 위해 첫 번째 배열을 이동합니다.

126 * 7은 최소 700은 넘기 때문에 계산할 필요도 없습니다. 숫자를 작게 만들기 위해 두 번째 배열을 이동합니다.

7 * 72는 504입니다. 두 번째 정답을 찾았습니다. 다음으로 넘어가겠습니다.

12 * 42 역시 504 입니다. 세 번째 정답을 찾았습니다. 다음으로 넘어가겠습니다.

54 * 36은 50 * 30만 계산해도 1500이 넘습니다. 숫자가 크기 때문에 작게 만들기 위해 두 번째 배열을 이동합니다.

54 * 14를 계산해야하지만 54 * 10만 생각해도 540이 됩니다. 아직 숫자가 크기 때문에 두 번째 배열을 이동합니다.

54 * 9는 계산해보면 486이 나옵니다. 숫자가 작기 때문에 더 크게 만들기 위해 첫 번째 배열을 이동 합니다.

72 * 9는 70 * 9만 해도 630으로 504보다 큰 숫자 입니다. 숫자를 작게 만들기 위해 두 번째 배열을 이동합니다.

72 * 7은 504로 네 번째 정답을 찾았습니다. 이제 다음 숫자들을 확인해 봅니다.

86 * 3을 계산해야 하지만 쉽게 90 * 3만 해도 270으로 504에는 한참 모자릅니다. 숫자를 크게 하기 위해 첫 번째 배열을 이동합니다.

124 * 3은 130 * 3만 계산해도 390으로 504보다 작기 때문에 첫 번째 배열을 이동합니다.

168 * 3은 504로 정답입니다. 이제 마지막 256 * 2를 계산해보면 512가 됩니다. 이렇게 5가지 경우가 정답이 됩니다.

계산이 많아서 귀찮을 수 있습니다. 무작정 경우의 수로 계산하기 보다는 규칙적으로 위치를 바꿔나가며 하나하나 따져가면 불필요한 계산을 하지 않고 정답을 얻을 수 있습니다.

 

2-5번

길이가 2칸인 다리에 10g만 버틸 수 있습니다. 따라서 어느 방향으로 더해도 10이 넘지 않는 경우를 만들어주면 됩니다.

가장 먼저 생각할 것은 9g은 1g을 더했을 때 10g이 됩니다. 1보다 작은 숫자가 없기 때문에 9g은 시작이나 끝인 부분에 무조건 존재해야 합니다.

끝 부분을 9라고 하면 두 번째 위치는 무조건 1이 됩니다. 8은 1과 2만을 좌, 우에 둘 수 있습니다. 따라서 1 다음에는 8, 그 다음은 2로 합니다. 7은 2와 3만을 좌, 우에 둘 수 있습니다. 따라서 다음은 7, 그 다음은 3이 됩니다. 이제 나머지 숫자 6과 4를 아무곳이나 배치하면 됩니다.

이러한 순서로 배치가 가능하고, 이것 말고도 9를 맨 앞으로 이동시켜 만들 수도 있습니다. 9와 마찬가지로 8을 맨 앞으로 이동시켜 배열시켜도 됩니다. 즉 이 문제는 위의 방법 외에도 여러가지 방법이 존재합니다.

2-6번

이러한 게임을 NIM 게임이라 합니다. 이 게임을 이기기 위해서는 무더기 A와 무더기 B의 나뭇가지 개수를 똑같이 만들어 주면 됩니다. 먼저 A에서 1개를 가져가 B의 개수 5개와 맞춰줍니다. 다음으로 상대방이 가져간 만큼 반대무더기에서 가져갑니다.

그럼 최종적으로 각 무더기에 1개씩 남게 됩니다. 상대방이 A나 B에서 하나 남은 나뭇가지를 가져가면 다음 턴에 나머지 하나를 가져오면서 승리하게 됩니다.

NIM 게임은 다양한 규칙이 있어 다른 규칙에서는 어떻게 하면 이길 수 있을지 생각해 보면 좋습니다.

2-7번

비버가 이동하는 경우의 조합을 생각해 보겠습니다. 왼쪽을 -로, 오른쪽을 + 로 표시하겠습니다.

첫 번째 이동	두 번째 이동	이동 합계
-3칸	2칸	-1칸
-3칸	7칸	4칸
-5칸	2칸	-3칸
-5칸	7칸	2칸

위와 같은 조합을 만들 수 있고, 이제 -2칸을 가는 것을 생각해보면 -3, +2칸 이동하면 -1칸 이동이 됩니다. 이것을 2번하면 총 4번 이동으로 왼쪽 2칸을 갈 수 있습니다.

아니면 오른쪽 7칸을 이동하고, 왼쪽 3칸을 3번 이동해도 왼쪽 2칸 이동이 가능합니다. 다양한 조합을 통해 어느것이 최소 이동 횟수인지 생각해 보면 쉽게 문제를 해결할 수 있습니다.

2-8번

서로 다른 두 전구를 사용해서 5번만 켜지도록 해야합니다. 즉 눌러야 하는 버튼의 시작과 끝이 5번만 빼고 모두 똑같게 만들어 주면 되는 것입니다.

예를 들어 2, 3번을 누르면 1, 2에 불이 들어오게 됩니다. 이제 5번 2번을 누르면 5번만 켜지고 1, 2번은 꺼지게 됩니다.

이 방법 뿐만 아니라 다양한 방식으로 만들 수 있습니다. 4번 1번을 눌러 3, 4, 5번만 불이 켜지게 합니다. 그리고 3, 4번을 누르면 5번만 켜지게 됩니다.

이렇게 다양한 방법이 가능합니다. 그 외 조합을 생각해보면 아래와 같은 방법이 있습니다.

[(2, 4), (4, 2)], [(3, 4), (4, 1)], [(5, 2), (2, 3)], [(4, 2), (2, 4)]