Diary/퍼즐-아군살리기 페이지의 소스 보기

내용출력
로그인[l]
수정할 수 없습니다: Diary/퍼즐-아군살리기 는 읽기 전용 페이지입니다.
#TEMPLATE [[Diary/DynamicTemplate]]
<div class="diary">
== [[/퍼즐-아군살리기]] ==

우연히 재미있는 문제를 보았다.

[http://211.228.163.31/30stair/ally/ally.php?pname=ally 아군 살리기]

일단 놀란 건 n에 관계없이 항상 답이 존재한다는 점이고...

막상 프로그램을 짜서 답을 내보니,
* n=3일 때는 간격이 5이지만
* n=4, 즉 8명을 세워놓고 뒤에 네명만 잡을 때는 간격이 30으로 뛰고
* n=13, 26명일 때는... 250만이 넘더라... (26명을 세워놓고 "어.느.것.을.고.를.까.요"하면서 손가락을 250만번 움직이는 걸 상상하니...)
뭐 이게 답이 맞는지 확인은 못 했지만 아마 맞겠지ㅋ

일단 구하는 코드는 짤 수 있는데 그 다음은 얼마나 빨리 답을 찾을 수 있느냐가 문제인데...

* 구해야 하는 간격 x는, 당연히 n보다는 클 거다. 안 그러면 첫번째에 아군이 죽으니까.
* 그럼 n+1 부터 시작해서 1씩 늘려나가면서, 그때마다 첫 적군부터 잡기 시작해서 마지막 적군까지 성공하는지 안 하는지 검사하는 방법이 가장 느린 방법일 테고
* 적군이 둘 남았을 때와 하나 남았을 때의 관계에서, x가 'n+1의 배수'이거나, 'n+1의 배수 + 1'의 형태란 건 알아냈다.
{{{
아아아...아적적
             ^ 이 적군을 잡았다면,
               n+1의 배수만큼 이동하면 마지막 적군을 잡을 수 있다
아아아...아적적
           ^ 이 적군을 잡았다면,
             한 칸 이동한 후에 n+1의 배수만큼 이동하면 마지막 x를 잡을 수 있다
}}}
** 따라서 검사할 대상을 2/(n+1)로 줄이는 데까지는 성공했는데...
* 검사할 대상을 더 줄일 수 있을까? 적군이 셋 남은 상태까지 거슬러가기만 해도 경우의 수가 6가지로 늘어서 꽤나 헷갈린다.
* 아니면 어떤 공식 하나가 있어서 n값을 넣으면 바로 답이 튀어 나올까?

마지막 의문. '''이 글을 보고 질문에 답을 주실 훌륭한 분이 계실까?''' :-)
<mysign([[Raymundo]],2012-11-28 1:46 am)>

===== Comments & Trackbacks =====

지금 봤는데, 답이 항상 존재하는 건 쉽게 보일 수 있네요.  \\
 \\
총 2n명이 있으니까, 원하는 수 x의 조건은  \\
 \\
2n mod x = n + 1 \\
(2n - 1) mod x = 1 \\
(2n - 2) mod x = 1  \\
(n + 1) mod x = 1 을 만족하는 수는 Chinese Remainder Theorem을 사용하면 항상 있기는 하죠. 그런데 이 수 x가 최소라는 보장은 없습니다... <mysign(inboklee,2012-12-31 2:58 pm)>

아차차, 써놓고 보니 CRT를 쓸 수 없네요. 조금 더 생각해봐야겠네요. <mysign(inboklee,2012-12-31 3:00 pm)>

: 어... \\
 \\
2n mod x 가 아니라 x mod 2n 이어야 하는 거 아닌가요? \\
게다가 그 결과가 n+1일 필요도 없고 0이거나 n+1부터 2n-1사이의 아무 수라도 되고... <mysign([[Raymundo]],2012-12-31 3:57 pm)>

예, 방향이 반대라는 걸 잊었는데, 단지 저런 답이 있다는 것만은 저렇게 보일 수 있고 답이 옵티멀인건 좀 있다가... <mysign(inboklee,2013-1-1 12:27 am)>

: 오오 훌륭한 분 오오. 기대하겠습니다, 제가 이해를 할 수 있어야 할텐데. <mysign([[Raymundo]],2013-1-1 12:35 pm)>

사실 말씀하신 방법대로, branch and bound를 이용하면 두가지 - 여섯가지 - 에서 안되는 것들을 계속 쳐내가면 답을 구할 수 있습니다. "좀 있다가..."라고 했지만 제가 요새 너무 바빠서 ㅠㅠ <mysign(inboklee,2013-1-4 11:39 am)>
<longcomments(100)>
----
[[주인장분류]]
</div>
Diary/퍼즐-아군살리기 페이지로 돌아가기 | 다른 수정본 보기