[백준] 28682번: 재우야 임관하자 JAVA

몬티홀 문제, 결론은 바꾸는게 확률이 높다.

문제

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

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

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

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

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

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

총 1,500개의 독립적인 평행 세계가 존재해 각 평행 세계의 재우는 위의 결정을 해야 한다. 각각의 평행 세계에 대해 프로그램 시작 시 재우가 Pass를 받을 과목 하나가 독립적으로 1/3 의 확률로 결정된다.

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

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

입력

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

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

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

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

예제는 평행 세계가 n=4개 존재할 때의 예시이며 예제는 채점하지 않는다. 실제로 프로그램은 n=1,500개인 입력에 대해서 정확히 한 번 실행된다.

예제 입력

먼저 4개의 과목을 출력하면, 컴퓨터가 각각의 평행 세계에 대해 그 과목을 제외한 나머지 두 과목 중 F를 알려준다.

이를 입력 받고, 각각의 평행 세계에 대해 최종적으로 Pass를 받은 것으로 예상되는 과목을 출력한다.
 

노트

인터랙티브 문제의 경우 출력을 하고, 언어에 따라 아래와 같은 명령어를 바로 다음에 적어 출력 버퍼를 flush해 줘야 한다.

C: fflush(stdout);
C++: fflush(stdout); 혹은 std::cout << std::flush;
Java: Syste m.out.flush(); 
Python: sys.stdout.flush()
Kotlin: Syste m.out.flush() 
남은 두 과목 중 하나를 고르게 되므로 재우가 Pass를 받을 확률이 1/2인데 어떻게 1,500개 중 900개나 예상할 수 있는지 의문을 가질 수 있다. <D.P. 시즌 1> 4화의 몬티홀 문제를 설명하는 허치도 병장과 관련된 다음 두 장면을 보며 그 방법을 알아보자.

장면 1(군대 내 후임과의 대화에서)
 - 치도 : 자, 여기에 세 개의 문이 있어. 이 문들 중 하나를 열고 들어가면 5박 6일 포상 휴가증이 있어. 영식이 하나 골라 봐.
 - (영식이 1번 문을 고른다)
 - 치도 : 오케이, 영식이가 1번 문을 골랐어. 근데 고르고 보니까 3번 문이 꽝이라는 걸 알게 됐어. 그럼 내가 다시 한번 물어볼게. 영식이 너는 계속 1번 문을 고른 선택을 유지할래? 아니면 2번 문으로 바꿔 볼래?
 - 영식 : 안 바꿉니다. 안 바꿉니다, 안 바꿔요.
 - 치도 : 왜? 내가 속일까봐? 아니면 바꿨다 휴가증 없으면 멘붕 오니까?
 - 영식 : 에이, 어차피, 뭐 반반 무 많이 아닙니까? 있거나, 없거나.
 - 치도 : 진짜? 자, 답은 ...

 장면 2(대학교 수업 중)
 - 치도 : 정답은 ‘선택을 바꿔야 한다’입니다.
 - 교수 : 나와서 설명해 봐.
 - 치도 : 통계학에 근거합니다. 최초 세 개의 문 중 하나를 골랐을 때 당첨될 확률은 1/3
 - (최초 고른 문을 제외한 한 문에 X를 치고, 둘을 묶어 +기호를 그린다)
 - 치도 : 다른 하나가 꽝인 걸 알고 선택을 바꾸게 됐을 땐 반반이 아닌 2/3 의 확률이 됩니다. 첫 선택 후 알게 된 꽝이라는 변수는 제가 처음 어떤 문을 선택했느냐에 따라 영향을 받고 달라지는 거니까요, 고로 정답은 ‘선택을 바꿔야 한다’입니다.
 - 교수 : 정답.

따라서 선택을 바꾸면 재우가 Pass를 받을 확률이 2/3 확률이 되며, 1,500개의 평행 세계 중 Pass를 받는 평행 세계의 기댓값은 1,000개다.

즉, 위의 전략처럼 처음 출력한 것과 다른 선택을 하게 되면, 평균적으로 1,500개 중 1,000개를 맞을 것을 기대할 수 있다는 의미이다.

만약 정말 운이 좋지 않아 해당 전략을 사용했음에도 900개 미만을 맞을 확률을 계산해보면, 0.00000286%정도로, 이 확률은 어떤 사람이 평생 로또를 딱 한번 샀는데 1등에 당첨될 확률(약 0.0000123%)보다 약 4.3배 정도 낮으므로, 혹시나 해당 전략을 사용했는데 틀렸다면 한 번 더 제출한 뒤 오늘 로또를 사도록 하자.
 
https://www.acmicpc.net/problem/28682

28682번: 재우야 임관하자

 

접근

몬티홀 문제이다.
서론이 길지만, 결론은 처음 선택을 바꾸는 것.
3개의 선택지 중, 처음 선택과 Fail 맞은 과목이 아닌 과목을 선택하여 출력하면 된다.
처음 선택을 swimming으로 고정시키고,
Fail 맞은 과목이 아닌 다른 과목을 출력한다.
 

구현

 

package 백준;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

//https://www.acmicpc.net/problem/28682
public class 재우야임관하자 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		//0) 기본 세팅
		//과목명
		String[] lectures = {"swimming", "bowling", "soccer"};
		//과목명의 idx를 맵에 삽입
		Map<String,Integer> map = new HashMap<String, Integer>();
		for(int i=0;i<lectures.length;i++) {
			map.put(lectures[i], i);
		}
		//1) 과목 선택
		int n = Integer.parseInt(br.readLine()); //시행횟수(1500)
		//처음에는 0번(swimming)만 제출
		for(int i=0;i<n;i++) {
			bw.append(lectures[0]+" ");
		}
		bw.append("\n");
		bw.flush();
		//2)  답 받기
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			//F 받은 과목
			String failLecture = st.nextToken();
			//0번과 F받은 과목이 아닌 1개의 과목을 출력한다
			int idx = map.get(failLecture)==1?2:1;
			bw.append(lectures[idx]+" ");
		}
		bw.close(); //답 출력
		br.close();
	}
}