/퍼즐-아군살리기

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

[아군 살리기]

일단 놀란 건 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값을 넣으면 바로 답이 튀어 나올까?

마지막 의문. 이 글을 보고 질문에 답을 주실 훌륭한 분이 계실까? :-)

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가 최소라는 보장은 없습니다...

아차차, 써놓고 보니 CRT를 쓸 수 없네요. 조금 더 생각해봐야겠네요.

어...

2n mod x 가 아니라 x mod 2n 이어야 하는 거 아닌가요?
게다가 그 결과가 n+1일 필요도 없고 0이거나 n+1부터 2n-1사이의 아무 수라도 되고...

-- Raymundo 2012-12-31 3:57 pm

예, 방향이 반대라는 걸 잊었는데, 단지 저런 답이 있다는 것만은 저렇게 보일 수 있고 답이 옵티멀인건 좀 있다가...

오오 훌륭한 분 오오. 기대하겠습니다, 제가 이해를 할 수 있어야 할텐데.

-- Raymundo 2013-1-1 12:35 pm

사실 말씀하신 방법대로, branch and bound를 이용하면 두가지 - 여섯가지 - 에서 안되는 것들을 계속 쳐내가면 답을 구할 수 있습니다. "좀 있다가..."라고 했지만 제가 요새 너무 바빠서 ㅠㅠ

이름:  

Homepage:

내용:
 

---

주인장분류