티스토리 뷰



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마리를 희생시키면서 독이든 와인을 확인할 수 있습니다.


댓글
  • 프로필사진 재훈 저기여 그 정보올림피아드 문제를 다운로드 받아서 보니 생쥐문제 저 15번 문제의 답이 2번이라고 나왔네요 오류인가요??
    2015.06.20 20:10
  • 프로필사진 야라바 저의 경우에도 문제를 풀고 나서 보니 다운로드한 파일의 답이 달랐는데 그래도 풀이 과정이 맞다면 답은 10일수밖에 없습니다. 다른 풀이 과정이 있어서 8이 나온다면 댓글로 알려주세요. 2015.06.22 10:49 신고
  • 프로필사진 재훈 음.. 제 생각이지만 저기서 최대 몇마리의 쥐가 "필요한가" 가 아니라 희생이니 10마리가 모두 희생한다면 와인은 1024잔이어야하니까 가장 많이 죽는 경우는 999번 째병 0011 1110 0111때문일까요?? 물론 제 생각입니다! 2015.06.22 19:02
  • 프로필사진 야라바 말씀을 듣고 다시 생각해보니 10은 N의 값이고 K값은 9가 되겠네요. 고맙습니다. 포스팅 수정했습니다. 혹시 이것도 아니면 말씀해 주세요 2015.06.22 21:50 신고
  • 프로필사진 ㅇㅇ 그냥 1000마리한테 다 먹이고 1명만 죽이면 안 될까요?
    왕이면 쥐 천 마리정도야 가뿐할텐데, 왜 굳이 저렇게 어렵게 풀려는지 ㅋㅋ
    2016.02.23 13:12
  • 프로필사진 123 한자리는 쥐에게 먹이지 않고, 안약 다른 쥐가 전부 죽지 않는다면 해당 비트를 가진 와인에 독이 있는 것 아닐까요? 2016.03.12 18:21
  • 프로필사진 ..... 저기 문제에 쥐 한마리 한테 1회만 와인 주입가능하다고
    되어있는데 근데 각 쥐한테 와인을 여러번 주입하시나요?
    2016.03.27 13:30
  • 프로필사진 야라바 여러번 마시게 할 필요는 없고 각 생쥐별로 그릇을 하나씩 두고 각 와인병의 숫자에 해당하는 비트 값이 1인 생쥐의 그릇에 아주 조금씩 따라서 혼합시켜서 먹이면 되겠지요. 질문 고맙습니다. 다시한번 검증해 보는 기회가 되었네요. 2016.03.28 08:57 신고
  • 프로필사진 이거.. 와인이 1000병인데 검증할수 있는 숫자는 1024개니까
    1이 9개인 것들이 24개 이하이므로 1000개 뒤의 1이 9개 이하인 예비번호로 보내버려서 8개라고 하네요

    이걸 어떻게 풀라는건지 ㄷ
    2016.04.03 11:03
  • 프로필사진 야라바 고맙습니다. 그런 아이디어가 있었군요. 글을 보완했습니다. 2016.04.04 11:42 신고
댓글쓰기 폼