|
:: 게시판
:: 이전 게시판
|
- 모두가 건전하게 즐길 수 있는 유머글을 올려주세요.
- 유게에서는 정치/종교 관련 등 논란성 글 및 개인 비방은 금지되어 있습니다.
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
22/09/27 09:13
(수정됨) 얼마전에 유튜브에서 봤는데 정말 신기하더군요.
모범수가 없으면 약 30% 정도의 확률로 석방 될 수 있고, 모범수가 있으면 100% 확률로 석방될 수 있습니다. 아, 제가 본 유튜브에서는 전원 석방 아니면 전원 사망이였습니다.
22/09/27 09:27
슬쩍 훑어본바로는 따로 약속을 만들어서
무조건 첫번째 상자를 먼저 열어보게하고 X번째 상자에 그 사람의 번호가 있다면 그 번호가 들어있는 상자랑 첫번째 상자를 바꾸면 최소한 한명은 확실히 살릴 수 있긴한데 모두를 살리는건 어떻게해야할지 고민을 해봐야겠네요
22/09/27 09:31
1. 모든 상자에서 홀짝 동일, 홀짝 불일치의 숫자를 센다
2. 어느쪽이 많은지는 1번 상자의 홀짝 동일 혹은 홀짝 불일치 스왑해서 정보를 남긴다. 이 정도면 거의 확실히 살 수 있지 않을까요?
22/09/27 09:34
좀 더 말하자면 죄수들은 1번을 열어보고 홀짝 동일이면 자신의 번호가 홀수 이면 홀수번호 상자만 열고
반대로 홀짝 불일치면 자신의 번호가 홀수 이면 짝수번호 상자만 열면 되는거죠.
22/09/27 09:39
(수정됨) 아닙니다. 홀짝동일 vs 불일치가 50:50이 가장 애매한 경우이지만 여기도 해법이 있을 것 같고
나머지 48:52, 46:54 같은 경우는 100% 살 수 있습니다.
22/09/27 09:41
(수정됨) 모범수가 홀수2개가 짝수 상자에 있는 상황을 파악했습니다. 어떻게 스왑해야 하나요?
모범수가 홀수3개가 짝수 상자에 있는 상황의 경우에는요? 안 될 것 같은데요.
22/09/27 09:43
[단 죄수들이 게임을 시작하기 직전에 모범수는 모든 상자들을 열어볼 수 있고 그 중 단 두상자의 내용물을 서로 바꿀 수 있다. ]
모범수는 모든 상자를 열어볼 수 있습니다.
22/09/27 09:46
열어볼 수 있지만 바꾸는 스왑은 딱 하나만 할 수 있습니다. 홀수20개가 홀수상자에 있고 나머지 30개는 짝수상자에 있는 상태라 합시다. 모범수는 스왑을 한번만 할 수 있습니다. 이 상황에서 홀수넘버 죄수가 입장한 상태에서 어떻게 자기의 넘버를 찾을 수 있을까요? 불가능합니다.
22/09/27 09:51
일치 20개가 불일치 30개면 불일치가 많으면 1번 자리에 불일치로 일치 자료 중 짝수를 스왑해 넣어두면 됩니다.
예를 들어 1번 상자에 숫자 2를 넣어두면 끝이죠. 홀수 죄수의 경우: 짝수 상자 49개(2, 4, 6, 8, 10, ...)를 뒤지면 자신의 번호가 항상 나옵니다. 짝수 죄수의 경우: 홀수 상자 나머지 49개(3, 5, 7, 9, 11)를 뒤지면 자신의 번호가 항상 나옵니다. 왜 안되는거죠?
22/09/27 09:53
1번을 열고나서 짝수 상자는 50개가 남아있고, 1번을 열어보는것도 상자를 열어보는거니 짝수 50명중에 누군가는 51번째에 자기 번호를 보게 되겠네요
22/09/27 10:00
이 경우도 가장 큰 숫자를 스왑 시키고, 50이상은 역순 이하는 정순 이런 식으로 51번째를 없애는 전략을 쓸 수 있을 것 같습니다.
22/09/27 09:56
불일치 30개일 때, 짝수상자 나머지를 뒤져서 자신의 번호가 나오는 홀수 죄수는 50명중에 30명밖에 없고 나머지 20명은 사형되는거 아니에요?
22/09/27 09:59
확률적으로 모든 홀수가 홀수상자에 있고 짝수가 짝수상자에 있을 경우는 극 소수이고 대부분이 불일치일 것 입니다. 이 상황에서 모범수는 (어쩌면 주나마나한 정보) 불일치한다는 정보를 주는 것이지요. 그러면 입장한 죄수는 불일치 한다는 것만 알지 자신의 넘버가 일치에 속하는지 불일치에 속하는지는 알 방법이 없어요.
3번죄수의 넘버가 5번에 상자안에 있습니다. 그런데 전체적으로 봐서는 불일치라면 3번죄수는 불일치니까 짝수를 몽땅 열게 될 것이고... 죽겠네요.
22/09/27 10:00
(수정됨) [풀이 - 간단 버전]
1. 죄수는 본인 번호와 같은 번호의 상자를 연다. 2. 상자 안에 들어있는 종이에는 상자와 다른 번호가 들어가 있다 3. 상자에 들어가 있는 종이에 적혀있는 번호의 상자를 연다. 4. 상자 안 에는 반드시 상자와 다른 번호의 종이가 있으므로 언젠가는 최초의 상자 번호가 적힌 종이(죄수 번호)가 들어있는 상자를 열 수 있다. 5. 모범수는 가장 긴 고리의 중간을 끊어주면 된다. 처음 보면 4번을 이해하는데 한참 걸립니다.
22/09/27 10:06
저도 요게 오래걸렸는데 가장 긴 고리가 1-100이 나란히 연결 된 수 밖에 없습니다.
그걸 끊어서 1-50 연결 두개로 바꿔주는 겁니다. 자연스레 남는 고리는 그것보다 작을테니.
22/09/27 10:09
1~4번까지 가는 건 숫자들로 연결된 하나의 고리를 만드는거라고 할 수 있습니다.
만약 고리의 길이가 50개가 넘게 되면 해당 고리에 속하는 죄수들은 모두 사형당합니다. 이떄 모범수가 50개가 넘기 전에 4-1 이 될 수 있게 고리의 중간을 끊어 준다는 느낌으로 숫자의 고리 중 가장 긴 고리에서 서로 반대 방향에 있는 두 상자의 숫자를 바꿔 주면 절반 길이의 숫자 고리 2개가 생기게 되고 모든 죄수가 석방 될 수 있습니다.
22/09/27 10:14
저런식으로 회귀 루프를 만들면 보통은 랜덤하게 여러개의 작은 루프가 생기는데, 재수 없을 경우 100개가 다 돌아가는 루프가 생길 수 있고, 그러면 50회의 시도 안에 자기 번호를 찾을 수가 없게 됩니다. 그걸 2등분으로 쪼개면 50개짜리 루프 2개가 되서, 50회 이내에 자기 번호를 찾을 수 있게 되고요. 어떻게든 한 번의 시행으로 가장 큰 루프가 50 이하로 되게 바꿀 수 있어요.
22/09/27 10:13
1번 상자에 1번 종이가 불가능한가요?
또한 하나의 긴 리스트가 아니라 여러개의 분리된 리스트, 혹은 순환도 가능하니까 2번이 참이 될 수 없고 3번을 실행할 수 없는거 같습니다만. 10개짜리 고리가 10개가 있을 경우 해결이 안될거 같아요.
22/09/27 10:15
그 순환하는 걸 이용하는 겁니다. 왜냐하면 내 번호 x 번으로 시작해서 돌다보면 순환해서 돌아와서 내 번호 x 를 지정하는 박스를 찾게 되고 그게 곧 석방의 조건이니까요. 어떤 숫자를 고르던지 순환은 100 회 이내가 되는데, 모범수가 바꿔치기 하는 행위는 순환 고리가 50회 이내가 되도록 하는 겁니다.
1번 상자에 1번 종이면 1번 죄수가 열어보고 바로 석방이죠. 이런 건 1개짜리 루프 (순환) 이고요.
22/09/27 10:21
왜냐하면 내 죄수번호 x 번 박스로 시작하면 내가 시작한 루프 내에 x 번 박스를 지정하는 x 숫자가 반드시 들어 있습니다. 이게 핵심이죠. 루프를 여러 개 시도할 필요 없이 내가 시작한 루프에 내 번호가 반드시 들어 있습니다.
22/09/27 10:22
여러번 선택할 필요가 없습니다.
자신의 번호가 적힌 상자를 열어서 시작하면 순환되기 때문에 순환의 마지막에 자신의 번호가 적인 종이를 뽑을 수 있습니다. 다만 이떄 순환의 길이가 50을 넘으면 사형이기 때문에 모범수가 순환 중간을 끊어서 절반 길이로 순환되는 두개의 고리를 만들어 주면 되는거고요.
22/09/27 10:24
내 번호 상자부터 시작하는 게 내 번호가 있는 루프를 고르게 되는 거더군요.
어떤 루프를 다 돌았는데 루프에 있는 상자 번호의 쪽지가 안 나올수는 없게 되어서..
22/09/27 10:26
자기 번호가 적혀있는 상자를 열게되면, 그 루프에는 무조건 자기 번호가 적혀있는 쪽지가 들어있습니다.
루프가 만들어질 수 밖에 없는 상황에서, 자기 번호 박스를 가리키는 종이가 어느 박스엔가는 들어있겠죠. 그 박스가 포함된 루프를 찾기 위한 방법이 자기 번호 박스를 시작으로 하는 루프에 탑승하는 거죠.
22/09/27 10:20
제가 봤던 영상에서는 상자에 적힌 번호와 다른 번호의 종이가 들어가 있었어서 그 기준으로 풀이를 적었습니다.
1번 상자에 1번 종이면 그거로 석방이라 상관 없습니다. (1개 짜리 고리가 생겼다고 생각하시면 됩니다.) 일단 모든 숫자는 끊어지지 않고 순환하게 됩니다. 상자와 종이의 숫자는 1:1 매칭이 되기 때문에 언젠가는 원래의 상자번호가 적인 종이가 나오게 됩니다. 순환이 끊어진다는건 5번 종이가 나왔는데 5번 상자에 5번 종이가 또 나오는 경우에 가능한데 이거는 상자와 종이가 1:1 매칭이 된다는 전제조건을 만족하지 않습니다. 따라서 모든 숫자는 어떠한 순환 되는 고리안에 들어가 있게 되고, 이때 죄수는 자신의 번호와 같은 상자를 열어서 순환을 따라 가면 마지막에 자신이 열었던 상자와 같은 번호가 적힌 종이를 뽑을 수 있게 됩니다.
22/09/27 10:28
솔직히 한참 고민하다가 답이 안 나와서 정답 동영상을 보고 한방에 이해했습니다.. 크크크..
방법을 알면 매우 간단해 보이는데, 논문 쓸 만 한 주제더라구요... 1000만명의 죄수도 1명의 모범수가 100% 살려줄 수 있는 이런 아름다운 문제는 언제나 환영합니다. (물론 정답도 같이 주셔야 합니다?!)
22/09/27 12:01
(수정됨) 가장 긴 루프를 만드는 쉬운 방법은 번호 + 1을 넣어놓는거죠
그럼 1번은 1(2) 2(3) 3(4) 4(5) 순서대로 열다가 50번(51)에서 죽습니다 자기 번호는 100번(1)에 들어있는데요 나머지 숫자들도 같은 방법으로 죽습니다 그러면 50번(51)과 100번(1)의 쪽지를 바꿔버리면 1(2)~50(1)까지 루프와 51(52)~100(51)까지 루프 2개가 생깁니다 아무리 멀리가도 50개를 까면 내것이 나오는군요 이제 실제 번호를 순서를 가진 문자열로 치환해서 루프를 따져보고 51이 넘는 루프만 끊어주면 됩니다 51이 안넘는건 안전한 루프고 넘는 루프는 1개 이상 나오지 않으니까요 설명을 듣고 극단적으로 밀어보니까 이해가 되네요
22/09/27 12:05
앞이 상자 번호, 뒤 쪽지 번호라 했을때
1(2) 2(3) 3(4) ......... 50(51) 51(52) ............99(100) 100(1) 최대 100루프인 경우 51번 죄수부터는 죄다 몰☆살인 상황에서 1(52) 2(3) 3(4) ......... 50(51) / 51(2) ............99(100) 100(1) 루프를 절반으로 줄이면 모든 죄수가 50번만에 제 번호를 찾게 되네요. 직접 써보고 이해했습니다. 크크
22/09/27 15:51
오랜만에 알고리즘 문제 푸니까 재밌네요 크크
directed graph의 Cycle 최대길이를 50 이하로 만들면 된다라고 생각하니까 이해가 확 되네요.
|
||||||||||||||