백준 인터랙티브 문제

드디어 백준에도 인터랙티브 문제들이 생겼다.

Codeforces에 이따금 출현하는 인터랙티브와는 사뭇 다른 느낌인데, 코포에서는 입출력을 통해 통신(?)을 한다면 백준은 함수 호출을 통한 인터랙티브를 사용한다.

 

삼성 B형에도 이따금 출제되는 유형이기도 하니, 코딩테스트를 목표로 하는 사람이라면 한번쯤 풀어보아도 좋을 듯 하다.

 

뒹굴면서 페북을 보다가, 인터랙티브 테스트 대회라고 있길래 후다닥 해보았다. 비공식 대회지만 처음으로 1등했다.. ㅋㅋ

내가 잘했다기보다는 잘하는 사람들이 크게 관심을 안가진 덕이 크다.

 

백준 18158. What an Easy Problem

생략. 문제를 잘 읽읍시다.

18158.cpp

 

 

백준 18159번. Have You Ever Sorted an Array?

1~n으로 구성된 길이 n의 순열 a가 주어질 때, 다음과 같은 질의(a[i]와 a[j] 중 어떤 것이 더 큰지)를 최소한으로 하여 순열을 알아내는 문제이다.

당연히 운좋으면 1번만에 맞출 수도 있으니 각 수열에 대한 최솟값을 물을 수는 없고, 여러 수열들에 대해 질문의 최대 횟수를 최소화시키는 것이다.

 

알고리즘 수업을 잘 들었다면 알 수 있지만, 이 문제는 sorting을 하는 과정와 깊이 연관되어 있다.

비교를 통한 sorting을 할 때 그 하한은 $O(n \log{n})$인데, 그 이유는 무엇일까?

왜냐하면 한번의 비교를 할 때, true 혹은 false 두 가지의 결과만을 얻게 되므로 최대 두 가지의 상태를 구별해낼 수 있다.

k번의 비교를 할 경우 최대 $2^k$가지의 상태를 구별해낼 수 있고, 이 값이 순열의 갯수보다는 커야 하므로 $2^k \gt n!$이고 양변에 로그를 씌우면 대략적으로 $k \gt n \log{n}$이 되는 것이다.

 

아무튼 이 아이디어를 가져오면, 예컨대 n = 7일 경우 $2^{13} >= 7!$이 되므로 최소한 13번의 질문은 필요할 것임을 알아낼 수 있다.

 

첫 질문은 뭐로 하던지 상관없으니 그냥 1번째와 2번째를 비교하는 것으로 하고, 두번째 질문부터는 후보들이 최대한 균등하게 나누어지도록 질문을 하면 (놀랍게도) 최소치가 가능한 것을 확인했다. 이대로 구현했더니 맞았다.

 

참고로 전처리를 해두어야 시간초과가 안 난다.

18159.cpp

 

 

백준 18160번. 숫자 야구

꽤나 유명한 문제이다. 숫자야구의 룰은 다들 알 것인데, 중복없는 n개의 숫자를 순서대로 골랐을 때, 정답과 위치까지 같으면 1S, 포함만 되면 1B이다.

다행히도 18159번처럼 최솟값을 묻지는 않으므로, 훨씬 느슨한 문제이다. 다만 이 문제는 시간초과를 줄이기 조금 힘들 수 있다.

 

전형적인 해법은, 모든 후보군들을 만들어놓고 ($_{10}P_7 = 5040$개의 후보가 있다) 질의를 적당히 하나씩 날려가며 질의에 해당하지 않는 것들을 지워나가면 된다. set<string> 등을 쓰면 아주 편하다. 이렇게만 해도 충분히 좋은 횟수가 나온다.

 

문제는, T = 5040이고 <S, B>을 체크하는 데에 최소 20번의 연산이 들어가므로, 5040 * 5040 * 20 = 5억이므로 시간초과이다. 적절한 전처리를 하는 것이 관건인데, 가장 시간이 많이 소요되는 부분은 맨 처음 5040개의 후보에서 후보군을 지워나갈 때가 되므로, 아예 set<string> [5][5]처럼 25개의 set을 만들어놓고 첫 질의 결과에 따라 가져와서 사용하면 시간을 많이 줄일 수 있다.

메모리가 넉넉하므로, 아예 처음에 질의를 2개 보내고 set<string> [5][5][5][5]처럼 더 많이 만들어놓으면 시간을 조금 더 많이 줄일 수 있다.

18160.cpp