2015년 정보올림피아드 진법 문제 풀기

1. 1에서 10까지의 자연수를 모두 곱한 수를 X라고 하자. X를 8진수로 표기하면 제일 오른쪽에 연속으로 나타나는 0은 모두 몇 개일까?

① 1 ② 2 ③ 4 ④ 6 ⑤ 8

※ 1부터 N까지의 자연수를 모두 곱한 수를 N 팩토리얼이라하고 N!로 표기하는데 10!은 1부터 10까지를 모두 곱한 값입니다. 10!를 8진수로 변환해야 하는데 값도 크고(10!은 3,628,800) 시간을 단축할 필요가 있으므로 팩토리얼을 아래의 그림과 같이 적절하게 분해하는 것도 방법이겠습니다.

자연수인 10진수를 N진법으로 변환하는 과정은 10진수를 N으로 나누면서 그 나머지를 취하면 되는데 10!에서 8로 나누면 나머지는 0이고 몫은 8이 빠진 7! x 9 x 10이 됩니다. 또 8로 나누어야 하는데 2 x 4로 나누면 나머지는 0이고 몫은 3 x 5 x 6 x 7 x 9 x 10이 됩니다. 그런데 이 값은 8로 더이상 나누어지지 않고 0이 아닌 나머지가 생깁니다. 고로 제일 오른쪽에 연속으로 나타나는 0은 두개입니다. 실제로 10! 값 3628800을 8진수로 변환하면 15657400입니다.

15. KOI 왕국의 통치자인 King Suryal은 마음씨가 좋다. 어느 날 King Suryal은 첩보를 통해 왕국 와인 저장고의 1000병의 와인 중에 한 병에 독이 들어 있다는 사실을 알아내었다. 하지만 어떤 와인 병에 독이 든 것인지는 알 수가 없었다. King Suryal은 부하들을 죽일 수는 없어서 생쥐 N마리에게 와인을 먹여서 독이 든 병을 찾기로 했다. 첩보에 의하면 독이 든 와인은 독이 너무나 강력하여 다른 와인과 섞어 얼마만큼 희석을 시킨다 하더라도 마신 후 정확히 30일 후에 무조건 사망한다고 한다. King Suryal은 오늘로부터 정확히 30일 후에 있을 축제에 와인을 사용할 예정이므로 각 생쥐에 와인을 먹일 수 있는 횟수는 1회이다. 많은 생쥐를 사용하지 않으려하므로 N을 최소화했다고 한다. 이 N마리의 생쥐 중 어떤 경우에라도 최대 K마리만을 희생시키려고 한다. 가능한 K의 최솟값은 얼마인가?

① 1 ② 8 ③ 9 ④ 10 ⑤ 999

※ 이 문제는 2진수를 활용하여 독이 든 포도주를 찾는 문제로 인터넷에 널리 알려진 기법입니다. 문제 출제자가 "King Suryal"이라 이름하여 이 원리를 모르시는 분은 무슨 수열을 찾아야 하나하고 머리가 아플 수도 있지만 알고 보면 단순하게 풀수 있는 문제입니다. "어떤 경우에라도"를 유념해야 합니다. 즉, 임의의 한개를 선택해서 찾는 방법은 배제되는 것이지요. 원리는 천개의 와인병에 1부터 1000까지 번호를 부여하고 각 번호를 이진수로 변환합니다. 이진수의 각 자리에는 특정한 생쥐를 할당하고 와인병 번호를 이진수로 변환한 각 자리수가 1인 경우 해당 생쥐에 와인을 아주 조금씩 먹입니다. 와인병이 1000개가 아니라 7개인 경우에는 아래의 그림과 같습니다.

6번 와인을 예로 들면 이진수로 110이므로 두번째와 세번째 생쥐에 와인을 조금씩 먹이는 것입니다. 이와 같은 방식으로 하면 각 생쥐는 그림과 같이 7개의 와인병인 경우에는 각각 4회씩 와인을 마시게 됩니다. 그래서 3마리가 모두 죽은 경우에는 7번 와인에 독이 있는 것이고 1번 2번만 죽은 경우에는 3번 와인에 독이 있는 것을 확인하는 방식입니다. 이런 방식으로 1000개의 와인병을 검사하려면 최소 10마리의 생쥐가 필요합니다. 십진수 1000은 이진수 1111101000이고 최소 10비트가 필요하기 때문입니다. 문제에서 N의 값은 10입니다. 그런데, 문제에서 최대 K마리만 희생시켜려하고 가능한 K의 최소값을 묻는 질문이므로 1000번 와인병에 독이 있는 경우는 1111101000이므로 6마리가 희생되고 10자리 이진수에서 1000보다 작은 값중에 1인 비트가 가장 많은 경우는  0111111111(511), 101111111(767), 1101111111(895), 1110111111(959), 1111011111(991) 로 최대로 희생시키는 K값은 9입니다. 그런데, 여기에서 저같은 사람은 생각하지 못했던 기발한 아이디어가 하나 있더군요(댓글 도움) 1인 비트수가 9인 값들을 1000~1024 사이에서 비트수가 9가 아닌 값으로 대체하는 방법입니다. 예를 들어 0111111111(511)->1111101001(1001), 101111111(767)->1111101010(1002), 1101111111(895)->1111101011(1003), 1110111111(959)->1111101100(1004), 1111011111(991)->1111101101(1005)와 같이 바꾸어서 와인을 섞으면 최소 10마리의 생쥐가 필요하지만 최대 8마리를 희생시키면서 독이든 와인을 확인할 수 있습니다.