https://www.clien.net/service/board/park/11075014?po=3&od=T31&sk=&sv=&category=&groupCd=&articlePeriod=defaultCLIEN 에 있는 문제의 답입니다.
옛날에 구글 입사 문제, MS 입사 문제 등으로 많이 유행하던 문제들 리스트가 있었는데,
그 중 한 문제네요.
다만, 문제의 조건이 좀 빠져 있습니다.
해적들은 전부 합리적인 생각을 하며, 해적들은 돌아가면서 배분 방안을 말한다는 조건이 빠져 있습니다.
만약 해적이 5명(A/B/C/D/E)이 있다면, A가 절반이 만족하는 답안을 말하지 못하면 A는 죽고,
나머지 4명의 해적이 차례대로 다시 배분 방안을 말해나간다는 규칙이 빠져 있네요.
그리고 원래 문제는 '어떤 방안을 내놓을 것인가'가 아니라
해적 5명이 있고, 금화 100개가 있을 때 첫 번째 해적이 '최대한 가져갈 수 있는 금화의 개수'는?
과 같은 금화 개수를 묻는 질문이었을겁니다.
추가된 조건을 보고 좀 더 생각해보실 분들은 더 생각을 해보시고...
답이 궁금하신 분들은 아래로 스크롤하세요.
만약 금화가 100개이고, 해적이 총 5명이라면... (A, B, C, D, E 라면)
마지막에 D/E만 남으면 D는 금화 100, E는 금화 0개를 제시하게 됩니다.
과반수를 만족하니깐 이대로 끝나는 거고, E는 금화를 하나도 획득하지 못합니다.
즉, E는 자기가 금화 1개 이상만 가지게 되면 무조건 이득입니다.
따라서 중간에 자신이 금화 1개 이상 받는 제안이 나오면 무조건 찬성을 할 것입니다.
이제 한 단계씩 이전 상황으로 진행을 해보면
만약 C/D/E가 남으면 C는
C:99, D:0, E:1 을 제시하면 됩니다.
만약 E가 찬성을 안 하면, 과반수 찬성이 안되므로 C가 죽고
D/E가 남으면 E는 금화를 하나도 획득 못하니깐요.
B/C/D/E가 남으면 B는
B:99, C:0, D:1 E:0 을 제시하면 됩니다. D는 찬성할 수 밖에 없습니다.
다음 번에 C/D/E가 남으면 D는 0개를 먹으니깐요.
A/B/C/D/E 이면 A는
A:98, B:0, C:1, D:0, E1 을 제시하면 됩니다.
C는 찬성을 해야 합니다. B/C/D/E가 남으면 C는 금화를 하나도 못 먹으니깐요.
즉, 첫 번째 제시하는 사람이 제일 많이 획득할 수 있는 금화의 양은 98개입니다.
