C++로 해결하는 과제 전달 문제: 감독관의 감시를 피해 과제 넘기기

이 튜토리얼에서는 감독관에게 들키지 않고 과제를 전달할 수 있는 방법을 찾는 알고리즘을 작성해 보겠습니다. 모든 학생은 한 줄로 앉아 있으며, 각자 자신의 과제를 감독관에게 제출해야 합니다. 그런데 A학생의 과제가 B학생의 손에 들어 있는 상황입니다. 따라서 B학생은 감독관에게 발각되지 않도록 과제를 A학생에게 되돌려주어야 합니다.

모든 학생은 한 줄(큐)로 앉아 있습니다. 우리는 과제를 들키지 않고 A학생에게 되돌려주는 방법을 찾아야 합니다. 과제를 주고받을 수 있는 조건은 다음과 같습니다.

A학생(인덱스 i)은 바로 옆에 앉은 학생, 즉 인덱스 (i-1) 또는 (i+1)에 있는 학생에게만 과제를 전달할 수 있습니다.
학생은 과제를 건네주거나, 받거나, 자신이 계속 가지고 있을 수 있습니다.
감독관은 [il, rl] 범위에 있는 모든 학생을 감시합니다.
감시 범위 안에 있는 학생은 과제를 보내거나 받을 수 없습니다.
반면, 감시 범위 안에서 과제를 그대로 소지하고 있는 것은 적발되지 않습니다.

입력으로 네 개의 값 p, q, r, s가 주어집니다. 여기서 p는 전체 학생 수, q는 감독관의 감시 구간 정보 개수, r은 과제를 처음 가지고 있는 학생(B)의 위치, s는 과제를 받아야 하는 학생(A)의 위치입니다.

각 감시 구간(q)마다 세 가지 입력이 주어집니다.

감독관이 해당 구간을 감시하기 시작하는 시점(시간)
감독관이 감시하는 구간의 왼쪽 경계(포함)
감독관이 감시하는 구간의 오른쪽 경계(포함)

출력은 "Left", "Right", "Keep" 세 단어로 구성된 시퀀스여야 하며, 각 단어는 학생의 행동, 즉 과제를 왼쪽 또는 오른쪽으로 전달하거나 그대로 가지고 있는 것을 나타냅니다. 예를 들어 다음과 같습니다.

예제

입력

출력

Right
Keep
Right
Right
Right
Right

설명

이 지시를 순서대로 따르면, 과제는 인덱스 2에 있는 학생에서 인덱스 7에 있는 학생까지 들키지 않고 전달됩니다.

입력

5 1 1 3
1 2 5

출력

Keep
Right
Right

설명

이 지시를 따르면 과제는 인덱스 1의 학생에서 인덱스 3의 학생에게 무사히 전달됩니다.

해결 접근 방법

핵심 아이디어는 간단합니다. 특정 시점에 감독관이 감시 중인 범위에 현재 과제를 가진 학생이나 과제를 받을 학생이 포함되어 있다면, 해당 학생은 과제를 그대로 유지합니다(Keep). 반대로 감시 범위 밖이라면, 최종 목표 지점을 향하는 방향의 인접 학생에게 과제를 전달합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
void solve(int p, int q, int r, int s,
long t[], int l[], int ar[]){
   int dir;
   string val;
   if (r < s) {
      dir = 1;
      val = "Right";
   } else {
      dir = -1;
      val = "Left";
   }
   string answer = "";
   int i = 0, current = r;
   long tim = 1;
   while (1) {
      if (i < q && tim == t[i]) {
         if ((current >= l[i] && current <= ar[i]) ||
         (current + dir >= l[i] && current + dir <= ar[i])) {
            answer += "Keep\n";
            tim++;
            i++;
            continue;
         }
         i++;
      }
      current += dir;
      answer += val+"\n";
      tim++;
      if (current == s)
         break;
   }
   cout << answer << endl;
}
int main(){
   int p = 8, q = 3, r = 2, s = 7;
   long t[q + 2] = { 1,2,3 };
   int l[q + 2] = { 4,1,5 };
   int ar[q + 2] = { 6,8,6 };
   solve(p, q, r, s, t, l, ar);
   return 0;
}

출력

Right
Keep
Right
Right
Right
Right

마무리

이번 튜토리얼에서는 감독관에게 들키지 않고 과제를 전달하는 알고리즘을 C++ 코드와 함께 살펴보았습니다. 같은 로직은 Java, Python 등 다른 프로그래밍 언어로도 충분히 구현할 수 있습니다. 이 알고리즘은 경쟁 프로그래밍 대회에서 자주 활용되는 중요한 유형으로, 실생활에서 접할 수 있는 문제 상황을 C++ 코드로 해결하는 좋은 예시이기도 합니다. 이 튜토리얼이 여러분께 도움이 되기를 바랍니다.