PGR21.com
- PGR21 관련된 질문 및 건의는 [건의 게시판]을 이용바랍니다.
- (2013년 3월 이전) 오래된 질문글은 [이전 질문 게시판]에 있습니다.
통합 규정을 준수해 주십시오. (2015.12.25.)
Date 2021/07/08 18:30:09
Name veteus
Subject [질문] quiz2) 100인의 죄수 (수정됨)
어제에 이어 두번째 퀴즈입니다.

죄수 100명이 있다.  게임이 시작되면 죄수들은 전부 각자 독방에 들어가며, 서로 의사소통 할 수 없다. 그리고 무작위로 죄수가 한명씩 불러나와 전구가 하나 있는 작은 방으로 간다. 작은 방에는 전구와 스위치만 하나 있으며 죄수는 전구를 끄거나 킬 수 있고 가만히 놔둘수도 있으며 잠깐의 시간을 갖고 다시 독방으로 돌아간다. 그리고 죄수가 독방으로 돌아가면 다시 무작위 죄수가(한번 불렸던 죄수가 또 불릴수도 있음) 불려 작은 방으로 잠깐 들어갔다가 돌아간다.
게임을 시작하기 전 작은 방에 있는 전구는 꺼져있고 죄수들은 모두 그 초기상태를 알고 있다.

규칙>
1. 죄수들은 스위치를 조작하는 것 이외의 어떤 흔적도 남길 수 없다.
2. 죄수들이 불릴 횟수에는 제한이 없고 지금 현재 몇명이나 불려나갔는지 등의 일체의 정보는 알 수 없다.
3. 죄수들은 누구라도 언제든지 게임을 중단할 수 있는데, 만약 중단 시점에서 모든 죄수가 한번 이상은 작은 방에 들어갔다 나왔다면 전원이 통과하고, 한명이라도 작은 방에 들어가지 않았던 죄수가 있으면 전원 실패한다.
4. 게임 시작 전 죄수들은 모두 모여 작전을 짤 수 있는 시간을 가진다.
5. 랜덤하게 불리기 때문에 무한한 시간이 지나면 모두 방을 방문하겠지만 이 문제는 그런 관점에서 보는 것이 아니라 확실한 해법이 있다.

죄수들은 어떤 전략을 세워야 할까요?



정답이 나왔으므로 문제를 조금 더 어렵게 하나 더 추가합니다.

위의 문제는 최초의 전구상태를 모두 알고 있는 경우입니다.  만약 최초에 꺼져있는지 켜져있는지 모를 때는 어떻게 하면 될까요?
위문제를 푸셨다면 이것도 어렵지 않게 풀 수 있습니다.

통합규정 1.3 이용안내 인용

"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.
법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
40년모솔탈출
21/07/08 19:09
수정 아이콘
불을 끄는 1인,
들어가서 불이 꺼져 있으면 1번만 불을 켜는 99인
불을 켜는 99인은 자신이 들어가을때 불이 꺼져 있으면 한번만 불을 켜기 때문에 99번 불이 켜집니다.
불을 끄는 1인은 99번 불을 끄면 자신을 제외한 99명이 들어갔다 나온 것이기 때문에 그때 게임을 중단하면 됩니다.
파란무테
21/07/08 19:14
수정 아이콘
무슨말인지 모르겠어요
21/07/08 19:20
수정 아이콘
(수정됨) 1번 죄수 : 불이 꺼져있으면 그대로 유지
불이 켜져있으면 끄고 그만큼 인원 수를 셉니다.
2번부터 100번 죄수 : 불이 켜져있으면 놔두고, 불이 꺼져있으면 최초로 한 번만 켜고 이후에는 아무 것도 하지 않습니다.

이렇게 되면 2번부터 100번이 최초로 한 번만 켜는 것을, 1번은 끄면서 카운트를 할 수 있습니다. 순서와 상관없이 나머지 99명은 한번씩만 불을 켜는게 보장되어 1번이 나머지 99명을 세고 게임 중단을 외칠 수 있습니다.
은때까치
21/07/08 19:23
수정 아이콘
죄수번호 1~100까지 지정 후, 불은 무조건 1번이 켜는 것으로 합니다.
1번을 제외한 모든 사람은 "첫 입장시" 불이 켜져 있으면 끄고, 그렇지 않으면 가만히 있습니다.
긴 시간이 지나고 1번이 다시 방에 들어왔을 때, 불이 꺼져 있으면 count ++ 하고 다시 켭니다.

이를 반복해서 count = 100이 되면 1번이 중단을 선언합니다.
21/07/08 19:33
수정 아이콘
(수정됨) 정답이 나왔네요.

한명의 카운터를 둡니다.

1. 카운터 : 불이 꺼져 있으면 그냥 나옵니다. 불이 켜져 있으면 불을 끄고 자신의 카운트숫자에 1을 더합니다. (이 숫자는 이 방을 방문한 사람입니다).

2. 나머지 죄수들 :
입장시 불이 켜져 있으면 그냥 둡니다.
입장시 불이 꺼져 있다면 불을 켭니다. 이 행위는 카운터에게 내가 왔음을 알리는 행위이므로 단 한번만 합니다. 즉, 이미 불을 켠 적이 있다면 불이 꺼져 있더라도 그냥 나옵니다.

카운터는 최초 0에 시작하여 99가 되면 자기를 제외한 모든 이가 방문했음을 확신하고 중단시킬 수 있습니다.
21/07/08 19:37
수정 아이콘
이때 철수를 구하시오.
21/07/08 19:39
수정 아이콘
철수는 간수입니다??
은때까치
21/07/08 20:01
수정 아이콘
추가문제 풀이: 거의 비슷하지만, 모든 죄수가 불을 2번씩 끄면 됩니다.

죄수번호 1~100까지 지정 후, 불은 무조건 1번이 켜는 것으로 합니다.
다른 모든 죄수들은 첫번째, 두번째 입장시 불이 켜져 있으면 끄고, 그렇지 않은 모든 경우 가만히 있습니다.

1. 첫 전구가 on인 경우: 최초에 불을 끈 죄수를 B라고 하겠습니다. 그러면 B는 1번, 나머지는 모두 2번씩 끄게 되면 count = 197이 됩니다. 197이 되면 1번이 게임을 끝냅니다.
2. 첫 전구가 off 인 경우: 198까지 셀 수 있지만 어쨌든 197을 센 시점에서 1번이 게임을 끝냅니다. 상관없거든요.
21/07/08 20:03
수정 아이콘
정답입니다. 해설도 완벽합니다.
은때까치
21/07/08 20:03
수정 아이콘
재밌게 풀었습니다~ 직접 내신건가요?
21/07/08 20:08
수정 아이콘
아니요 저도 어디선가 본 문제에요.
목록 삭게로! 맨위로
번호 제목 이름 날짜 조회
156644 [질문] 윈도우 10 초기화 후 먹통 [2] 공백13383 21/07/13 13383
156643 [질문] 쉬엄쉬엄 할만한 PC 게임 없을까요 [16] 우들9725 21/07/13 9725
156642 [질문] 헬스하는데 패턴이 이상합니다. [15] 젤리롤10435 21/07/13 10435
156641 [질문] 야경 및 야간에 바람쐬고 힐링하기에 좋은 경주 명소 알려주세요. [7] 기술적트레이더14372 21/07/13 14372
156640 [질문] 에초질문 (에초병님들 봐주세요) [4] 알파고9874 21/07/13 9874
156639 [질문] 롤토체스를 배우고 싶은데 어디서 배우는게 가장 좋을까요 [8] Dark9375 21/07/13 9375
156638 [질문] LH 청년주택 입주 청소 맡기는 게 괜찮을까요? [9] Robbie8242 21/07/13 8242
156637 [질문] 언어마다 난이도가 다른가요?? [26] 레너블13048 21/07/12 13048
156635 [질문] so1 스타리그 vod 풀버전으로 볼 수 있는 곳 있을까요? [10] Graves10014 21/07/12 10014
156634 [질문] 웃으면 안되는 상황에서 웃음 못참는걸 일컫는 단어가 있나요? [9] 쁘띠도원10424 21/07/12 10424
156633 [질문] 서울 소재 중소기업 다니시는 분들, 재택 많이 하시나요? [30] 無我12769 21/07/12 12769
156632 [질문] 운전면허 취득 후! [9] 스윗N사워12551 21/07/12 12551
156631 [질문] 싼타페 하이브리드 구매에 대해 질문 드립니다. [19] 나를찾아서15342 21/07/12 15342
156630 [질문] 컴퓨터 하드웨어 관련 질문입니다. [4] Like a stone8461 21/07/12 8461
156629 [질문] SSD 복구 관련된 질문드립니다. [9] 애플댄스8299 21/07/12 8299
156628 [질문] 회사 식당에 코로나환자가 나왔습니다 [20] 삭제됨10055 21/07/12 10055
156627 [질문] 옵션과 차급 어디에 비중을 두시는지요 [34] 熙煜㷂樂12323 21/07/12 12323
156626 [질문] 월세 바닥 장판 문제 [2] 아밀다10361 21/07/12 10361
156625 [질문] 진입후 정상적으로 신호가 바뀔경우? [6] 나른한오후9706 21/07/12 9706
156624 [질문] 주택담보 대출 관련 질문 [3] akroma9063 21/07/12 9063
156623 [질문] 화이자 1차 접종 후 언제까지 2차를 맞아야하나요 ? [10] -Aka12264 21/07/12 12264
156622 [질문] 그래픽카드 업글시 발열이 체감될 정도로 낮아질까요? (RX580) [9] 마니에르8209 21/07/12 8209
156621 [질문] 저사양 사무용 PC 이륙견적 부탁드립니다. [2] 장만월9486 21/07/12 9486
목록 이전 다음
댓글

+ : 최근 1시간내에 달린 댓글
+ : 최근 2시간내에 달린 댓글
맨 위로