구글의 입사 면접 질문

저기서 1퍼센트는 ssr이라고하면 좋다고 달라들겠네

머리에 평등과 분배라는 개념이 없는 사람 아닐까...

해적에게 논리가 필요할리가

문제조건에 평등하게 라는 말이 없잖아
그리고 해적이면 아마도 계급제일텐데 평등 자체가 힘든 상황이 아닐까
그리고 귱극적 목적은 과반수 이상의 지지만 이끌어내면 되는거고

질문이 원래 저게 다가 아님.
목표가
1) 죽지 않고
2) 그와 동시에 자기 자신이 받는 금을 maximize 하는거
1번만이 목적이면 당연히 답이 저렇게 단순해 지는데, 2번때문에 어려워지는 문제임.
옛날에 마이크로소프트 면접 질문이라며 how to move a mount fuji 에 소개되었던 문제임.
원문에 해적수는 또 5명이라고 명시해 놓음.
그 경우 저 목표 2개를 다 이루는 분배법은 {1, 0, 1, 0, 98}
설명은 여기: http://www.mytechinterviews.com/5-pirates-fight-for-100-gold-coins
참고로 현재 마소도 그렇고 구글도 그렇고 저런 brain teaser 질문들은 더이상 면접때 안물어봄

일단 정확히 원문제는
1. 해적은 모두 5명; 해적1, 해적2, 해적3, 해적4, 해적5.
2. 이중 해적5이 랭크5로 가장 급이 높음. 그담으로 해적4가 랭크4, 해적3이 랭크3.. 등등
3. 랭크 순으로 금 100을 어떻게 나눌지 제안한다. 그러므로 해적5가 먼저 제안.
4. 해적5을 포함한 해적 5명이서 그 제안을 절반이상 (>= 1/2) 찬성하면 분배완료.
5. 찬성이 < 1/2 면 해적5를 죽이고, 해적4가 남은 4명한테 분배 제안.
6. 분배가 완료될때까지 4-5 반복.
목적:
1. 해적5가 죽지않고
2. 해적5가 가지는 금을 maximize
답.
{1, 0, 1, 0, 98}
먼저 해적이 2명일 경우엔 답이 뭘지 생각해보자: 해적1, 해적2
그럴 경우 해적2가 금 100을 다 가져도, 해적2만 찬성을 해도 찬성조건 >= 1/2 충족.
2명의 답: {0, 100}
3명의 경우를 보자.
만약 해적3의 분배가 찬성조건을 못채워서 죽게되면 해적이 2명만 남는다. 이럴 경우 위의 해적2명 경우의 수와 같아져 해적1은 아무것도 받지 못한다.
그러므로 해적3은 해적1을 설득하기 위해 {1, 0, 99} 의 제안을 한다. 이렇게 되면 해적1의 입장에선 그래도 금1을 받는게 금0을 받는것 보단 나으므로 제안에 찬성을 하게된다.
3명의 답: {1, 0, 99}
4명의 경우를 보자.
만약 해적4의 분배가 찬성조건을 못채워서 죽게되면 해적이 3명만 남는다. 이럴 경우 위의 해적3명 경우의 수와 같아져 해적2는 아무것도 받지 못한다.
그러므로 해적2를 설득하기 위해 {0, 1, 0, 99} 의 제안을 한다. 이렇게 되면 해적2의 입장에선 그래도 금1을 받는게 금0을 받는것 보단 나으므로 제안에 찬성을 하게된다.
4명의 답: {0, 1, 0, 99}
5명의 경우를 보자.
만약 해적5의 분배가 찬성조건을 못채워서 죽게되면 해적이 4명만 남는다. 이럴 경우 위의 해적4명 경우의 수와 같아져 해적1,3은 아무것도 받지 못한다.
그러므로 해적1,3들을 설득하기 위해 {1, 0, 1, 0, 98}의 제안을 한다. 이렇게 되면 해적1,3의 입장에선 그래도 금1을 받는게 금0을 받는것 보단 나으므로 제안에 찬성을 하게된다.
5명의 답: {1, 0, 1, 0, 98}

1개 받은 놈들은 배신할 여지가 충분한데?
선장 죽이면 24개를 더 먹잖아?

감사합니다

아하, 해적들이 존내 2명 남을 때까지 죽을 걸 생각하고 통밥을 굴린다는 이야기야?

아니 포인트가 되는 즉, 1을 받는 해적은 금괴를 받거나 안받거나 선택이지만 98을 원하는 해적은 죽자나... 1을 받을수 있는 해적경우 너 죽을래 금괴 더 내놓을래 라고 딜 할정도의 머리가 없는거야

이건 수학적인 내용이고 감정이나 이성이 섞이면 되도않는소리잖아

해적이 몇명이던
그중 51%의 인원에겐 금괴를 나누어 주겠다 라고 몰래 약속을 해놓는거지

해적의 51%보다 금괴수가 더 적으면?

해적수를 줄여버리면 되지!

금괴수를 비밀로 해야지..
패를 다 까버리면 어케..

금괴수가 적을리는 없지
어차피 금괴는 1이든 100이든
나누기만 하면 되니까

녹이거나 자르면 안된다는 말은 없는데.

낄낄대며 만든게 아니고 전문가에게 맡긴거지..

천재네 ㅋ

선장이 먼저 곯아떨어져서 사망.