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
수정 아이콘
아니요 저도 어디선가 본 문제에요.
목록 삭게로! 맨위로
번호 제목 이름 날짜 조회
156612 [삭제예정] 팔이 부러진 경우 수술 관련 질문드립니다 [6] 삭제됨10468 21/07/11 10468
156611 [질문] 여자들도 좋아하는 남자향수 어떤 게 괜찮은지요..? [19] nexon13361 21/07/11 13361
156610 [질문] 넷플릭스에 지루하지 않은 영화 추천 부탁 드립니다. [12] 원스13138 21/07/11 13138
156609 [질문] 트위치 프라임 게이밍을 구독하면 광고를 안 볼 수 있나요? [4] 아타락시아112319 21/07/11 12319
156608 [질문] 스포티지 추천할만한가요? [4] 호구입니다12393 21/07/11 12393
156607 [질문] 직소 퍼즐 용 액자 추천 preeminence9675 21/07/11 9675
156606 [질문] 중학교 영어 인강 추천 부탁해요 [14] 슬리미12462 21/07/11 12462
156604 [질문] 로아 스토리 익스프레스 질문이용 [6] 롯토18590 21/07/11 18590
156603 [질문] 디지털카메라(디카) 관련 문의드립니다. [10] 판을흔들어라10417 21/07/11 10417
156602 [질문] 핸드폰 온라인 쇼핑몰에서 구매해도 믿을만 한가요? [2] nekorean9452 21/07/11 9452
156601 [질문] 입주청소와 줄눈 관련 질문 [6] Equalright9366 21/07/11 9366
156600 [질문] 텐트? 그늘막? 파라솔? 뭘 사야할지 고민중입니다. [10] 퀴즈노스13942 21/07/11 13942
156599 [질문] 70대 남성 금장 가성비 시계 추천 바래요 [3] 도뿔이9548 21/07/11 9548
156598 [질문] SKT에서 알뜰폰으로 이동해도 좋을까요? [8] 기록가17431 21/07/11 17431
156597 [질문] 팝송을 찾고 있습니다. [2] 쿨럭16973 21/07/11 16973
156596 [질문] 포장 이사+입주 청소 질문 드립니다. [5] 원스11154 21/07/11 11154
156595 [질문] 자동차 관리요소 중에 주기적 고속주행도 중요한가요? [12] purpleonline16629 21/07/11 16629
156594 [질문] 어라운드뷰살라는데 어떻게 사서 장착하면되나요? [3] 외계소년12033 21/07/11 12033
156593 [질문] 구글의 바다에서 이미지를 찾고있습니다. [7] 티타늄9624 21/07/11 9624
156592 [질문] 전주 막걸리집 중 괜찮은 곳이 있을까요? [3] 띵호와9576 21/07/10 9576
156591 [질문] 컴퓨터 메모리 사용 여부 문의합니다 [4] 틀림과 다름9165 21/07/10 9165
156590 [질문] 요근래 특정유저에게 쪽지 받으신분 있으신가요? [11] TAEYEON17833 21/07/10 17833
156589 [질문] 매력적인 여주인공 + 완전 명작 영화 추천 좀 부탁드립니다. [53] 기술적트레이더12244 21/07/10 12244
목록 이전 다음
댓글

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