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.0077 sec