재우야 임관하자

이 문제는 인터랙티브 문제이다. 아래 노트에 나와 있는 방식으로 입출력을 진행해야 한다.

2023년 2학기, 드디어 고려대학교에 드랍(수강포기제)이 부활한다! 이번 학기를 마치고 졸업하는 사이버국방학과 재우는 원래도 DP 문제를 좋아했는데, 최근에 시즌 2가 나온 드라마 <D.P.> 시리즈를 보고 졸업 후 장교로 임관하기로 마음먹었다. 재우는 임관을 위해 최대 3개까지 수강할 수 있는 운동 과목을 수강하기로 했다. 작년에 F를 받은 "수영" 과목의 재수강은 물론, "축구"와 "볼링" 과목까지 최대로 수강하게 되었다.

드랍을 할 수 있는 날이 다가오자, 재우는 갑자기 작년에 수영을 F 받은 기억이 떠올라 PTSD가 왔다. 이에 재우는 지도 교수님께 면담을 요청했다. 재우의 정보를 보던 교수님은 재우가 세 과목 중 두 과목을 F 받고 한 과목만 Pass를 받을 수 있다는 사실을 알게 되었다. 원래는 이를 알려주면 안 되지만, 재우를 딱하게 여긴 교수님은 한 가지 방법을 떠올린다. 재우가 좋아하는 <D.P. 시즌 1>에 나온 몬티홀 문제로 힌트를 주기로 한 것이다!

이제 재우는 다음과 같은 과정을 거쳐 정보를 얻을 수 있다.

1. 먼저, 재우가 Pass로 예상하는 과목 하나를 교수님께 말씀드린다.
2. 그러면 교수님께서 그 과목을 제외한 나머지 두 과목 중 F를 받는 과목 하나를 알려주신다.

재우는 이 정보를 바탕으로 두 과목을 드랍하고 남은 한 과목을 수강하기로 하였다. 재우는 남은 과목이 Pass이기를 원한다. 재우가 되어 그 과목을 찾아보자.

총 $1\,500$개의 독립적인 평행 세계가 있고, 각 평행 세계의 재우는 위의 결정을 해야 한다. 각 평행 세계에서 Pass를 받을 과목 하나는 프로그램 시작 시 $\frac{1}{3}$의 확률로 독립적으로 정해진다.

각 평행 세계에서 위의 1번과 2번 과정은 다른 세계와 독립적으로 진행된다.

아래 인터랙티브 과정을 거쳐 $1\,500$개의 평행 세계에 있는 재우 중 총 $900$명 이상이 최종적으로 예상한 과목이 프로그램이 정한 과목과 같아 Pass를 받으면 정답이다. 모든 평행 세계의 행동은 독립적으로 시행된다. 해답을 모르겠다면 아래 노트를 읽어보자.

프로그램이 시작되면 먼저 평행 세계의 개수 $n = 1\,500$을 입력받는다.

$n$개의 평행 세계마다 Pass로 예상하는 과목을 swimming, bowling, soccer 중 하나씩 골라, 공백으로 구분한 $n$개의 과목 이름을 한 줄에 출력한다. 이 출력 직후 flush한다.

그러면 프로그램은 각 평행 세계마다 고른 과목을 제외한 두 과목 중 F인 과목 이름을 하나씩 공백으로 구분하여 준다.

이 정보를 토대로 최종적으로 각 평행 세계마다 Pass로 예상하는 과목 이름을 공백으로 구분하여 한 줄에 출력한다. 이 출력 직후 flush한다.

인터랙티브 문제에서는 출력한 뒤, 언어에 맞는 아래 명령어로 출력 버퍼를 flush해야 한다.

• C: fflush(stdout);
• C++: fflush(stdout); 또는 std::cout << std::flush;
• Java: System.out.flush();
• Python: sys.stdout.flush()
• Kotlin: System.out.flush()

남은 두 과목 중 하나를 고르므로 재우가 Pass를 받을 확률은 $\frac{1}{2}$처럼 보인다. 그런데 어떻게 1,500개 중 900개 이상을 예상할 수 있을까? <D.P. 시즌 1> 4화에서 몬티홀 문제를 설명하는 허치도 병장의 장면 두 개를 보며 그 방법을 알아보자.

장면 1 (군대 내 후임과의 대화에서)

• 치도: 자, 여기에 문이 세 개 있어. 이 중 하나를 열면 5박 6일 포상 휴가증이 있어. 영식이 하나 골라 봐.
• (영식이 1번 문을 고른다)
• 치도: 좋아, 영식이 1번 문을 골랐어. 그런데 고르고 보니 3번 문이 꽝이라는 걸 알게 됐지. 그럼 다시 물어볼게. 1번 문을 계속 고를래, 아니면 2번 문으로 바꿀래?
• 영식: 안 바꿉니다. 안 바꿉니다, 안 바꿔요.
• 치도: 왜? 내가 속일까 봐? 아니면 바꿨다가 휴가증이 없으면 멘붕 올까 봐?
• 영식: 에이, 어차피 반반 아닙니까? 있거나, 없거나.
• 치도: 진짜? 자, 답은...

장면 2 (대학교 수업 중)

• 치도: 정답은 "선택을 바꿔야 한다"입니다.
• 교수: 나와서 설명해 봐.
• 치도: 통계에 근거합니다. 처음 세 개의 문 중 하나를 골랐을 때 당첨될 확률은 $\frac{1}{3}$입니다.
• (처음 고른 문을 제외한 문 하나에 X를 치고, 두 문을 묶어 +를 그린다)
• 치도: 다른 하나가 꽝인 걸 알고 선택을 바꾸면 반반이 아니라 $\frac{2}{3}$의 확률이 됩니다. 첫 선택 후 알게 된 꽝이라는 변수는 제가 처음 어떤 문을 골랐느냐에 따라 영향을 받고 달라지는 거니까요. 그래서 정답은 "선택을 바꿔야 한다"입니다.
• 교수: 정답.

따라서 선택을 바꾸면 재우가 Pass를 받을 확률은 $\frac{2}{3}$가 된다. $1\,500$개의 평행 세계 중 Pass를 받는 평행 세계의 기댓값은 $1\,000$개다.

즉, 처음 출력한 것과 다른 선택을 하면 평균적으로 1,500개 중 1,000개를 맞힐 것으로 기대할 수 있다.

이 전략을 써도 900개 미만을 맞힐 확률은 $0.00000286\%$ 정도다. 이는 평생 로또를 딱 한 번 산 사람이 1등에 당첨될 확률(약 $0.0000123\%$)보다 약 4.3배 낮다. 혹시 이 전략을 썼는데 틀렸다면 한 번 더 제출한 뒤 오늘 로또를 사 보자.