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

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

이전 문제는 아래 링크 확인 바랍니다.

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

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

2024.04.22 - [알고리즘 설명/정보올림피아드 필기] - 2022년 정보올림피아드 필기 중등부(11 ~ 15)

 

16번

초등부 19번과 같습니다. 아래 링크를 통해 19번 확인 바랍니다.

https://davincicoding.tistory.com/134#19%EB%B2%88

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

 

17번

 

 

초등부 20번과 같습니다. 아래 링크를 통해 20번 확인 바랍니다.

https://davincicoding.tistory.com/134#20%EB%B2%88

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

 

18번

NIM 게임과 같습니다. 양쪽의 돌이 똑같아지도록 균형을 맞추면 됩니다.

A에서 돌을 가져가면 B의 돌을 가져가 똑같이 맞춰줍니다. 마지막에 결국 A와 B에 각각 한개씩 남게 되고, 컴퓨터가 한쪽의 돌을 가져가면 당신이 남은 하나를 가져가 게임에서 이길 수 있습니다.

이 방법 외에도 다양한 방법으로 게임을 이길 수 있습니다.

 

19번

이진 최대공약수 알고리즘 혹은 스테인 알고리즘이라 불리는 문제 입니다. 최대 공약수를 구할 때 가장 많이 쓰이는 방법이 유클리드 호제법인데 스테인 알고리즘을 통해 구할수 있습니다.

두 수 a, b의 최대공약수를 gcd(a, b)라고 하겠습니다. 그럼 아래와 같은 규칙이 성립합니다.

• gcd(a, 0) = a

0은 모든 수로 나누어지고, a는 a로 나눌 수 있는 가장 큰 수 이기 때문에 위 공식이 성립합니다.

• gcd(a, b) = 2 * gcd(a / 2, b / 2) (a, b는 모두 짝수)

두 수 a, b가 모두 짝수라면 위 식이 성립합니다. a, b의 최대공약수에 2가 포함 되어 있기 때문에 두 수 모두 2로 나누어 구한다음 다시 2를 곱해주면 원래의 최대공약수가 됩니다.

• gcd(a, b) = gcd(a/2, b) (a는 짝수, b는 홀수)

a가 짝수일 때, b가 홀수일 때라고 했는데 a, b는 바뀌어도 상관 없습니다. 어짜피 b가 홀수이기 최대공약수의 약수에 2가 들어가지 않습니다. 따라서 a를 2로 나누어도 상관 없습니다.

• gcd(a, b) = gcd((a - b), b) (a > b이고 둘다 홀수)

두 수가 모두 홀수이고 a가 b보다 클 때 성립합니다. 최대 공약수를 x라고 한다면 다음과 같은 식이 성립합니다.

a = cx, b = dx, a - b = (c - d)x

a에서 b를 뺀다는 것은 cx - dx와 같습니다. 최대공약수 x는 변하지 않음을 알 수 있습니다. 유클리드 호제법을 알고 있다면 이해할 수 있습니다.

그럼 두 수의 최대공약수를 구하는 방법을 알아보겠습니다. 먼저 두 수 모두 짝수이기 때문에 2로 나누어줍니다. 둘 중 하나가 홀수가 나올 때까지 진행 합니다. 실행해보면 총 7번을 2로 나누어주었을 때 둘 중 하나의 수에 홀수가 나타납니다. 즉 2 ** 7 이라는 수가 최대공약수에 포함되어 있는 것입니다. 따라서 마지막에 최대공약수를 구하면 2를 7번 곱해주어야 합니다.

이후는 큰수에서 작은수를 빼주던가, 큰 수가 짝수라면 2로 나누어줍니다. 이것을 기계적으로 반복하면 40번대를 남겨두고 하나의 수에 0이 나옵니다.

그럼 남은 숫자에 2를 7번 곱해주면 아래와 같이 정답을 얻을 수 있습니다.

 

20번

8, 9 두 사람에게 1, 2가 같은지 물어봅니다. 그리고 나머지 사람들에게 8, 9가 같은지 묻습니다.

만약 8, 9번의 대답이 같다면 8, 9번은 둘 다 참이거나 거짓 입니다. 그럼 나머지 사람들에게 물은 8, 9번이 같은지 틀린지로 나머지 사람들의 참과 거짓을 알 수 있습니다. 그리고 1, 2번의 대답으로 8, 9가 참인지 거짓인지 알 수 있습니다.

위와 같이 질문을 했을 때 8, 9번의 대답이 같기 때문에 둘 다 참이거나, 거짓 입니다.8과 9가 같기 때문에 8 = 9라고 말한 사람들은 전부 참입니다. 그리고 8 ≠ 9라고 말한 사람들은 전부 거짓 입니다. 마지막으로 1과 2의 대답이 다릅니다. 따라서 8, 9번은 전부 거짓을 말하고 있습니다.