[PS/BOJ] 프로그래밍에서 인터랙티브 문제 푸는 법 (예제 풀이 포함)

이 포스트에서는 Problem Solving에서 가끔 등장하는 인터랙티브 문제에 대해 설명하고 푸는 방법을 간단하게 정리해보겠습니다.

 

인터랙티브(Interactive) 문제란 제출 코드에 따라 입력 데이터가 결정되는 문제입니다.

이름 그대로 채점 프로그램과의 상호 소통하는 방식을 통해 풀이해야 하는 문제 유형이라고 할 수 있습니다.

 

예를 들어 여러분이 다른 사람과 스무고개를 한다고 가정하면 상대방은 여러분이 어떤 질문을 하느냐에 따라 다른 답을 할 것이고, 그렇게 되면 얻은 답을 기반으로 내용을 유추하여 최종 답을 찾아야 합니다.

이러한 방식으로 문제를 풀이하는 것이 인터랙티브 문제라고 보시면 됩니다.

 

설명만으로는 이해하기 부족하기 때문에 인터랙티브 문제를 하나 풀이해보겠습니다.

적절한 난이도로 백준 Online Judge(BOJ)의 23306번 문제를 풀이해보도록 하겠습니다.

 

 

백준 BOJ 23306번 : binary는 호남선

 

문제에서 주어진 규칙에 따라 정해진 횟수 이내로 프로그램에 질의를 할 수 있고, 주어지는 답들을 가지고 구간 내에 오르막 구간의 수와 내리막 구간의 수를 비교해서 최종 답을 출력해주면 됩니다.

 

만약 1번 구간이 0이고 마지막 구간이 1이라면, 중간에 어떻게 연결이 되든 반드시 오르막 구간이 내리막 구간보다 하나가 많게 됩니다.

반대로 1번 구간이 1이고 마지막 구간이 0이라면, 중간에 어떻게 연결을 해도 내리막 구간이 하나 많습니다.

1번 구간과 마지막 구간의 높이가 같다면 오르막 구간과 내리막 구간의 수가 같게 됩니다.

 

이 원리를 이용하여, 1번 구간와 N번 구간의 높이를 물어보고 답을 얻는 인터랙티브를 통해 최종 답을 구해주면 됩니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);

    int N; cin >> N;

    cout << "? " << 1 << "\n"; fflush(stdout);
    int a; cin >> a;

    cout << "? " << N << "\n"; fflush(stdout);
    int b; cin >> b;

    if(a == 1 && b == 0) {
        cout << "! " << -1 << "\n"; fflush(stdout);
    }
    else if(a == 0 && b == 1) {
        cout << "! " << 1 << "\n"; fflush(stdout);
    }
    else {
        cout << "! " << 0 << "\n"; fflush(stdout);
    }
}

 

풀이 코드는 위와 같고, 해설은 다음과 같습니다.

 

먼저 구간의 수 N을 입력 받습니다.

그 다음 "? 1"으로 1번 구간의 높이를 물어보고, 변수 a에 저장합니다.

그 다음 "? N"(여기서 N은 변수)으로 N번 구간의 높이를 물어보고, 변수 b에 저장합니다.

위에서 설명한 원리대로 높이를 비교하여 최종 답을 "! (답)"으로 출력합니다.

 

참고로 인터랙티브 문제에서는 반드시 한 번 출력을 해준 다음에 다음 출력을 위해 출력 버퍼를 비워주어야 합니다.

따라서 출력을 해준 뒤 fflush(stdout)으로 버퍼를 비워줍니다. (또는 cout 뒤에 endl을 사용해도 버퍼가 비워집니다.)

 

 

 

cin.tie(NULL)과 cout.tie(NULL)이 있다면 지워주고 위와 같이 코드를 돌려서 채점 프로그램 대신 직접 숫자들을 입력하여 인터랙티브가 제대로 동작하는지 확인할 수 있습니다.

 

 

 

위와 같이 정답 처리를 받을 수 있습니다.

 

이 포스트에서 언급된 풀이 없이 스스로 연습을 해보려면 다음과 같은 아주 쉬운 인터랙티브 문제를 추천합니다.

 

18158번: What an Easy Problem