U E D R , A S I H C RSS

Basic알고리즘/빨간눈스님

Basic알고리즘/빨간눈스님

문제

{{| 옛날에 어느 나라에 승려들만 모여 사는 섬이 있다. 그들 중에서 어느 사람은 눈이 빨갛고 어느 사람은 눈이 갈색이다. 눈이 빨간 사람은 마법에 걸려 있기 때문에 스스로 눈이 빨갛다는 사실을 깨닫게 되면 그 날 밤 12시에 그 나라를 떠나서 사라져야만 한다. (무조건) 승려들은 서로의 눈 색깔에 대해 전혀 언급하지 안는다는 불문율이 있었기에 상대방의 눈 색깔을 알려줄 수도 없었따. 그 섬에는 거울도 없고, 거울 비슷한 물건도 없었기 때문에 자신의 눈이 무슨 색인지 아는 사람은 아무도 없었다. 그래서 그들은 자신의 눈 색깔을 알 길이 없었기에 행복하게 살아갈 수 있었으며, 그 나라를 떠나는 사람도 아무도 없었다. 그러던 어느날, 그 섬에 관광객이 찾아왔다. 그는 승려들 사이에 존재하는 규칙을 알지 못했기 때문에 절대로 하지 말아야 할 말을 내뱉고 말았다.
"당신들 중에서 적어도 한명은 눈이 빨간색이로군요"
무심한 관광객은 그 날로 돌아갔지만, 남아 있는 승려들은 생전 처음으로 눈 색깔에 대한 말이 나왔기 때문에 크게 동요하지 않을 수 없었다. 그리고 그 날 밤부터 그 섬에는 무서운 일이 일어나기 시작했다. 과연 어떤일이 일어났겠는가? |}}

제가 읽던 책에서 아주 재미있는 것을 발견하고, 이렇게 올려봅니다.
프로그래밍에서 알고리즘을 찾는 것과 유사하다고 저자는 말하고 있는데요, 알고리즘을 찾아봅시다 ㅋㅋ!! - 허아영

생각적기

상당히 좋은 문제입니다. 이 문제를 컴퓨터를 도구로 사용해서 해결을 하는 훈련을 하면 상당한 사고훈련이 될 것입니다. 적극 권합니다. 스스로 이 문제의 답을 알고 있다고 생각하는 사람도 직접 프로그래밍을 해보거나 하시면 많은 것을 느끼고 깨닫게 될 것입니다. --JuNe

이것은 허회장께서 요즘 보시는 책에 나와있는 문제군요 ㅋㅋ 재미있는 문제입니다. - 도현
감사합니다= 선배님들께서도 답을 생각해 보시고, 이 생각적기에 적어주시면 좋을 것 같은데요 ^^ -아영
  • 상협 의견 - 3가지 경우
    • 관광객이 거짓말한 경우 (눈이 빨간 스님이 아무도 없는경우) : 이 경우에는 모든 스님들이 섬을 떠나게 된다. 왜냐면 모든 스님들은 자신의 눈을 제외한 다른 사람들의 눈 색밖에 볼 수없는데 만약 다른 모든 사람들의 눈 색이 갈색이라면 자신의 눈 색이 빨간 색이므로 섬을 떠나야 한다고 생각하게 된다. 빨간색의 눈을 가진 스님이 아무도 없기 때문에 모든 스님이 이렇게 생각하게 된다.
    • 눈이 빨간 스님이 한분 있는 경우 : 이때 자신의 눈이 빨간 스님은 다른 모든 사람들의 눈이 갈색인것을 보고 자신의 눈이 빨갛다는 것을 알수 있고 섬을 떠나게 된다. 그리고 남은 스님들은 빨간 눈의 스님이 한분 떠난 것을 보게 된다. 그리고 각자 자신이 보는 다른 모든 스님들의 눈 색은 갈색인데, 적어도 한명은 눈이 빨간색이라고 했기 때문에 자신이 볼때 남은 스님들의 눈이 모두 갈색이더라도 자신이 100% 빨간 눈이라고 할수 없기 때문에 떠나는 스님은 없게 된다.
    • 눈이 빨간 스님이 여러명 있는 경우 : 이때는 자신의 눈이 빨갛더라도 다른 빨간 눈의 스님이 있는 것을 볼 수 있기 때문에 자신이 100% 빨간 눈이라고 확신할 수 없다. 떠나는 스님이 없게 된다.

  • 현태 의견 - 2가지 경우
    • 눈이 빨간 스님이 한분 계실때 - 그 한분이 자신임을 알고 떠나시게 된다.
    • 눈이 빨간 스님이 2분 이상일때 - 최소한 한명의 눈이 빨간 사람을 보게 되므로 자신이 눈이 빨갛다는 것을 확신할 수 없기 때문에 아무도 떠나지 않는다.
    • 전체적으로 상협형의 의견과 유사합니다. 글을 읽고 밑을 봤는데 형이 이미 의견을 올리셨네요. 다른 경우가 관광객이 거짓말을 한 경우인데.. 저의 경우는 관광객이 거짓말을 할 이유가 없다고 생각해서..;;;; 다름 섬에 갔을때 괜시리 '당신중에 한명 이상은 눈이 빨갛네요.'라고 할 이유는 없지 않을까요.

  • 너의 이론이 맞는지 직접 프로그래밍해서 실험해 보면 어떨까. --JuNe

답안지

책에 나온 답안지는 이렇습니다.
(관광객이 한 말이 참말이라는 전제로 문제를 풉니다.)
{{|
먼저, 관광객이 한 말인 "당신들 중에서 적어도 한명은 눈이 빨간색이로군요" 를 분석 해 보면, 빨간색의 눈을 가진 사람이 적어도 1명, 즉 1명 이상이라는 것을 알 수 있다.
그러므로 빨간눈을 가진 스님이 아무도 없다는 것을 전제로 하지 않는다.
  • 빨간눈을 가진 스님이 한 명일 경우, 빨간색 눈을 가진 스님의 시각에서 빨간눈을 가진 스님이 아무도 없다. 그럴경우 자신이 빨간눈을 가지고 있다고 알게되고, 그 날 밤 그 스님은 그 섬을 떠나게 된다.
  • 빨간눈을 가진 스님이 두 명일 경우, 빨간색 눈을 가진 두 스님들은 각자 자신들의 시각에 한사람의 빨간눈 스님이 보일 테므로, 그 날 밤 그 다른 스님이 섬을 떠날 것이라고 서로 생각하게 된다. 하지만 다음 날 아침 그 스님이 떠나지 않은 것을 알게되고, 빨간눈을 가진 각각 스님은 자신도 빨간눈인 것을 알게 된다. 그 날 밤 두 스님이 그 섬을 떠나게 된다.
  • 빨간눈을 가진 스님이 세명일 경우, 빨간색 눈을 가진 세 스님들 각자 자신의 눈에는 두명의 빨간눈 스님을 보게 될 것이다. 이 스님이 첫째날에도 안 떠나고, 둘째날 밤에 그 섬을 떠날 것이라 생각할 것이다. 하지만 다음날 아침, 떠나지 않은것을 보게되고, 자기자신도 빨간눈이구나 라고 알게 된다. 그래서 그 날 밤 세 스님이 떠나게 된다.
  • 그러므로 빨간눈을 가진 스님이 N명 일 경우, 한명의 스님이 그 스님들이 떠날 거라고 예상하는 기간은 N-1일이고, 자신이 만약 빨간색눈을 가졌더라면, N일 째 밤에 N명의 스님이 떠나게 됩니다.
|}}
제가 책 읽었던 것을 풀이해서 적었는데, 보완할 것이 있다면 덧붙일 내용에 적어주세요 ^^
아참, 코드 작성하면 재밌을 것 같아요 ! 코드 만들어봐요 ~~ ^^ - 아영

  • 이해가 안가는 부분 : 빨간눈 스님이 두명 이상일때부터..., 일단 두명일때 - 자신의 시각에서 빨간눈의 스님이 한분 보여서 그날밤 그 스님이 떠날거라고 서로 생각하는데 안떠났다고 했을때 그때는 빨간눈 스님이 최소 2명 이상이 된다. 그런데 이때 그 빨간눈 스님이 2명 이상이 된다고 해서 어떻게 빨간눈을 가진 스님은 자신이 빨간 눈인것을 알 수 있나.. 이해 안감..
    • 빨간눈 스님이 최소 두명인데.. 자기 눈에 보이는 빨간눈 스님이 한명이면.. 나머지 한명은 누구일까요?? 자기 자신이죠.. 이 규칙을 잘 지키려면 스님들이 머리가 좋아야 겠네요.
      • 움 알겠다. 오해였넹,,
* 관광객이 거짓말을 했을때도.. 답이 있었는데.............. 어쨌든 이 문제 진짜 재미있어서 예전에 봤는데 지금까지 기억하는 문제 +_+ --선호

코드

이름 언어 코드

덧붙일 내용

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:34
Processing time 0.0322 sec