구글 입사 면접 문제.

이게 정확한 풀이고 윗 댓이 젤 먼저 풀었네

아랫 사람은 풀이가 정확히 있는데 의미 없다고 하는 건 뭐냐;

처음 다섯마리 5경기를 하고 결과를 sorting했다고 치자 (어차피 문제엔 영향 X)

O O O X X
O O O X X
O O O X X
O O O X X
O O O X X

그 다음 1등끼리 달리게 되고 이걸 조를 또 sorting했다고 치자 (이번에도 영향 없음 개념적인 sorting이니깐)

1등 조 O O O X X
2등 조 O O X X X
3등 조 O X X X X
4등 조 X X X X X
5등 조 X X X X X
여기서 1등 조의 1등은 이미 총 1등이니깐 다음 검사가 필요한 것은

1등 조 A O O X X
2등 조 O O X X X
3등 조 O X X X X
4등 조 X X X X X
5등 조 X X X X X

O인 5개임 (여기서 2-3등)

이를 정리하면

5 + 1 + 1
총 7번

이거 안보고 푸는데 1분 정도 걸렸는데 오래 걸렸군...

아 ㅋㅋ 윗댓 내가 잘못봤구나 여튼 윗댓이랑 이 댓글이랑 내 댓글이랑 다 같은 말인데
이 댓글이 표식으로 잘 정리했네
3등 댓글 11번은 의미없다고 한거 반성 해야겠다

- ✨ 행운의포인트 주인공. 댓글작성 5 포인트 획득!

틀림.
1조에 12345등이 다있으면 위 7번으로 부족함

- ✨ 행운의포인트 주인공. 댓글작성 15 포인트 획득!

진짜 멍청하구나...

누가? 너가?

- ✨ 행운의포인트 주인공. 댓글작성 13 포인트 획득!

지다가다 설명드립니다.
1조 O ㅇ ㅇ ㅇ ㅇ
2조 O ㅇ ㅇ ㅇ ㅇ
3조 O ㅇ ㅇ ㅇ ㅇ
4조 O ㅇ ㅇ ㅇ ㅇ
5조 O ㅇ ㅇ ㅇ ㅇ
대문자 O를 각 조 1등이라하고 O끼리 경주했을때 빠른 순서대로 1부터 5까지 임의로 순번을 부여합니다. 여기까지 총 6번의 경주를 한겁니다. 각 조별 5번, 조별 1등끼리 1번.
여기서 각 조에서 1등을 뽑은 5번의 경주를 실험a라 하고 1등끼리의 경주 1번을 실험b라 하겠습니다.
실험a에서 각 조 4~5등은 제외됩니다. 그러면
1조 O o o x x
2조 O o o x x
3조 O o o x x
4조 O o o x x
5조 O o o x x
여기서 실험b를 진행했을 때 4조 1등말이 최고 4등, 5조 1등말이 최대 5등이라 4조,5조에 속한 말들도 전부 제외되고 3조는 3조의 1등이 최고기댓값 3등의 경우밖에 없으므로 3조 1등을 제외한 나머지 3조 말도 제외됩니다. 또한 1조 1등말이 가장 빠르기 때문에 2조에 속한 3등 말의 최대 기댓값은 4등입니다. 따라서 제외하면
O o o x x
O o x x x
O x x x x
x x x x x
x x x x x
1조 1등은 각 조1등과의 경주에서도 1등이므로 다음 시행에 참가시킬 필요가 없습니다. 따라서 대상에서 제외 시키면
x o o x x 1조 2,3등
o o x x x 2조 1,2등
o x x x x 3조 1등
x x x x x
x x x x x
이 5마리 중 1,2등을 뽑으면 총 7번 맞습니다.

님은 구글 못들어가실듯...

왜 그렇게 생각하시는 지 설명 부탁드려도 될까요?

아니 1조에 시속 5 4 3 2 1 인 말 5마리가 있고
2조부터 0.9 0.8 0.7 0.6 0.5
3조 0.4 0.3 0.2 0.1 0.09
4조 0.08 0.07 0.06~~

이런식으로 5조까지 쭉 있으면 너 방법대로면 제일 빠른말 3마리가 안나온다고요ㅋㅋ
7번경기해서 3마리 뽑으면 시속 5 , 0.4, 0.08 가 뽑히는건데 실제 순위랑 다르자나

이게답같다...

조별 1등하는게 왜 의미가 없어?
윗댓 방식은 2, 3등 뽑는데 오류가 있는데 7번은 맞음
안겹치게 각 그룹 A B C D E로 5마리씩 경주 -> 5번
각 1등말 5마리끼리 경주 -> 6번 경주, 전체 1등 나옴

이제 이 다음이 중요한데
일단 각 그룹의 4, 5등은 당연히 나가리고,
A그룹 1등이 1등, B그룹 1등이 2등, C그룹 1등이 3등이라면

D E 그룹은 볼필요도 없이 다 탈락임
D E에서 제일 빠른 말도 이미 발렸으니까

그리고 B에서 3등, C에서 2등, 3등한 말도 나가리임
이미 걔네보다 빠른말로 A 1등, B 1등이 있으니까
(B 2등은 C 1등보다 빠를 수 있음)

전체 1등인 A 1등말은 이미 순위 나왔으니 ㅂㅂ고
그럼 총 남은 말이 A 2등, A 3등, B 1등, B 2등, C 3등
딱 5마리임

얘네끼리 경주해서 2, 3등 뽑으면 됨. -> 7번째 경주

문제의 접근은 1,2,3 등 외에는 어짜피 순위를 다룰 필요가 없으니 소거법으로 하면 간단했다.

'일단 각 그룹의 4등 5등은 당연히 나가리고'←←←←←무슨 근거로?
A그룹이 개 헬지옥의 조편성이라 A조에서 5등한 말이 C조 1등말보다 빠를수도있는데?

1,2,3 등만 뽑는데 4, 5등은 당연히 나가리지
A그룹 5등이 뭐가 중요하냐 ㅋㅋㅋ
지보다 빠른말이 4마리나 있는데

아니 1조에 시속 5 4 3 2 1 인 말 5마리가 있고
2조부터 0.9 0.8 0.7 0.6 0.5
3조 0.4 0.3 0.2 0.1 0.09
4조 0.08 0.07 0.06~~

이런식으로 5조까지 쭉 있으면 너 방법대로면 제일 빠른말 3마리가 안나온다고요ㅋㅋ
7번경기해서 3마리 뽑으면 시속 5 , 0.4, 0.08 가 뽑히는건데 실제 순위랑 다르자나

- ✨ 행운의포인트 주인공. 댓글작성 13 포인트 획득!

진짜 멍청한 샛기...

- ✨ 행운의포인트 주인공. 댓글작성 11 포인트 획득!

니가 쓴 예시로 해볼까? 5조는 숫자 없는데 대충 1, 0.8, 0.6, 0.4, 0.2 라 해볼께
(숫자도 뭐 이리 그지같이 해놨냐..)

1조 1등 : 5 / 2등 : 4 / 3등 : 3
2조 1등 : 0.9 / 2등 : 0.8 / 3등 0.7
3조 1등 : 0.4 / 2등 : 0.3 / 3등 : 0.2
4조 1등 : 0.08 / 2등 : 0.07 / 3등 : 0.06
5조 1등 : 1 / 2등 : 0.8 / 3등 : 0.6
-> 여기서 5번 했고

1등말끼리 경주
1등 : 5 / 2등 : 0.9 / 3등 : 1 -> 이제 6번 경주

1조에서 1등말 / 5조에서 2등말 / 2조에서 3등말 나왔으니

1조 2등, 3등말 / 5조 1등말, 2등말 / 2조 1등말
이렇게 5마리가 경주 -> 이제 7번
(그 외의 말은 자기보다 빠른말이 3마리 이상 있음. ex) 2조 1등말의 경우, 적어도 1조 1등, 2조 1등, 5조 1등말 보다 느림)

7번 경주 결과
1등 : 1조 2등말(4) / 2등 : 1조 3등말(3) / 3등 : 5조 1등말(1)
-> 2조와 5조의 1등말은 1조의 2등, 3등말한테도 진걸 확인

따라서 전체 제일 빠른말은 1조의 1등, 2등, 3등말이고
5, 4, 3 인걸 확인함.

멍청하면 우기기라도 하지 말던가..
설명을 이해할 지능도 없으면 짜져있어

- ✨ 행운의포인트 주인공. 댓글작성 18 포인트 획득!

틀림
윗댓 방법으로 경기 11번이 답인듯
처음 5조로 나눌때 1조에 전체 123등이 다 있을때면 위 방법밖이 없는듯

다음과 같이 1조에 전체 123등이 다 있다고 할때
1조 : 1등, 2등, 3등, 말, 말
2조 : 말, 말, 말, 말, 말
3조 : 말, 말, 말, 말, 말
4조 : 말, 말, 말, 말, 말
5조 : 말, 말, 말, 말, 말

1번째 경기 : 1조 5마리 결과는 1등, 2등, 3등, 나머지 말
2번째 경기 : 2조 5마리 결과는 말 X 5
3번째 경기 : 3조 5마리 결과는 말 X 5
4번째 경기 : 3조 5마리 결과는 말 X 5
5번째 경기 : 3조 5마리 결과는 말 X 5
6번째 경기 : 각 조 1등말 (1등, 말, 말, 말, 말) -> 1등말 추출
7번째 경기 : 1조의 2등,3등, 2조의 1등, 2등, 3조의 1등 -> 1조의 2등, 3등 추출
답 7번

틀림 1조에 12345등이 다있으면 안됨

- ✨ 행운의포인트 주인공. 댓글작성 12 포인트 획득!

아니 1조에 시속 5 4 3 2 1 인 말 5마리가 있고
2조부터 0.9 0.8 0.7 0.6 0.5
3조 0.4 0.3 0.2 0.1 0.09
4조 0.08 0.07 0.06~~

이런식으로 5조까지 쭉 있으면 너 방법대로면 제일 빠른말 3마리가 안나온다고요ㅋㅋ
7번경기해서 3마리 뽑으면 시속 5 , 0.4, 0.08 가 뽑히는건데 실제 순위랑 다르자나

- ✨ 행운의포인트 주인공. 댓글작성 11 포인트 획득!

이런문제에 집착하는 정신 이상한애들 고를려고 내는거임

정답은 12번임<br />5마리씩 5번 경기해서 각조에서 두마리 탈락시킴<br />15마리를 다시 5마리씩 3번경기<br />9마리를 다시 5마리 4마리(1마리만 탈락) 2번경기<br />남은 6마리중 5마리를 1경기시킴<br />거기서 이긴 3마리를 나머지 한마리와 다시 경기 시킴<br />5+3+2+1+1= 12번

각 조 1등끼리 한번씩만 경주시키면 더 많은 변수를 제거 가능한데 왜 15마리씩 경주시켜서 손실을 보시는 건지 이해가 안갑니다. 탈락시키는 거에 초점을 두셨으면 각 조 1등끼리 경주시켜서 제거되는 변수를 찾아보시면 7번입니다

님처럼 생각하면 a조에서 5등걸려서 탈락한 말이 c조 1등보다 빠른경우의 수를 걸러내지못함

3마리 뽑는건데 a조 5등이 c조 1등보다 빠른 경우를 왜 따지는거지.
생각보다 빡대가리들이 엄청 많구나. 이게 7번이라고 저렇게 자세하게 설명을 해도 여기서 똥싸고 있네

최소 필요한 경기수가 무슨 말인지 모르나. 7이 12보다 작기 때문에 답은 7임.

아니 1조에 시속 5 4 3 2 1 인 말 5마리가 있고
2조부터 0.9 0.8 0.7 0.6 0.5
3조 0.4 0.3 0.2 0.1 0.09
4조 0.08 0.07 0.06~~

이런식으로 5조까지 쭉 있으면 너 방법대로면 제일 빠른말 3마리가 안나온다고요ㅋㅋ
7번경기해서 3마리 뽑으면 시속 5 , 0.4, 0.08 가 뽑히는건데 실제 순위랑 다르자나