/퍼즐-아군살리기

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

[아군 살리기]

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

이름:  

Homepage:

내용:
 

---

주인장분류