Two-step 유형 문제

Two-step 유형 문제는 풀이가 서로 단절된 두 번의 실행으로 쪼개져, 앞 단계가 남긴 쪽지 한 장만이 뒤 단계로 건너가는 형태입니다.

문제 해결 방식

Two-step 유형 역시 함수 구현 방식의 한 갈래이지만, 참가자가 채워야 할 함수가 둘이라는 점, 그리고 그 둘이 한 흐름 안에서 이어지지 않는다는 점이 특별합니다. 프로그램은 두 번에 나누어 실행되며, 각 실행은 한 함수씩만 맡습니다.

• 앞 단계(인코딩): 문제가 내준 데이터 전부를 살펴보고, 그 내용을 압축해 담은 쪽지(중간 메시지)를 만들어 둡니다.
• 뒤 단계(디코딩): 앞 단계가 남긴 그 쪽지 하나만 손에 쥔 채, 뒤늦게 날아오는 질문에 답합니다.

이 유형의 묘미이자 함정은, 두 단계가 기억을 전혀 공유하지 못한다는 데 있습니다. 앞 단계에서 아무리 공들여 계산하고 전역 변수에 쌓아 두어도 뒤 단계는 그것을 볼 수 없습니다. 뒤 단계가 의지할 수 있는 것은 오직 앞 단계가 쪽지에 적어 넘긴 내용뿐입니다.

감을 잡기 위해 다음 문제를 떠올려 봅시다. $N$개의 방이 한 줄로 늘어서 있고, 각 방은 1, 2, 3 중 한 색으로 칠해져 있습니다. 앞 단계는 모든 방의 색을 둘러본 뒤 쪽지를 작성합니다. 그러면 뒤 단계에 두 방 번호 $A$와 $B$가 주어지는데, 뒤 단계는 그 쪽지만 보고 두 방의 색이 서로 다른지 같은지를 가려 different 혹은 same으로 답해야 합니다.

까다로운 점은, 앞 단계가 쪽지를 쓰는 시점에는 나중에 어느 두 방을 비교하게 될지 전혀 모른다는 것입니다. 어떤 방이든 물어볼 수 있으니, 일부 방만 골라 적어서는 안 되고 결국 모든 방의 색을 빠짐없이 쪽지에 새겨 넣어야 합니다. 한 가지 방법은 방마다 "번호와 색을 한 덩어리로 묶은 수"를 적어 두는 것입니다. 이를테면 1번 방의 색이 1이라면 $1\times 10+1=11$처럼 적습니다. 그러면 뒤 단계는 쪽지의 각 수를 다시 번호와 색으로 풀어 헤친 다음, $A$번과 $B$번 방의 색을 꺼내 견주기만 하면 됩니다.

그래서 이 유형의 핵심은 한마디로 "뒤 단계가 답하는 데 필요한 모든 것을 앞 단계가 미리 쪽지에 담아 두는 일"입니다. 다만 쪽지의 길이나 적을 수 있는 값의 범위에 제한이 걸리는 경우가 많고, 같은 답이라도 더 짧은 쪽지로 해결할수록 높은 점수를 받기도 합니다.

IOI 환경과 제공 파일 (providing.zip)

Two-step 문제의 압축 자료에는 두 단계를 차례로 불러 이어 주는 채점기, 두 단계 각각의 스켈레톤, 그리고 이들이 같은 함수 모양을 공유하도록 묶어 주는 헤더가 들어 있습니다.

1. 헤더 파일 (twostep.h)

두 스켈레톤과 채점기가 함수의 생김새를 똑같이 알고 있도록 약속을 적어 둔 파일입니다. 앞 단계 함수 encode와 뒤 단계 함수 decode의 모양이 선언되어 있습니다.

#ifndef TWOSTEP_H
#define TWOSTEP_H

#include <string>
#include <vector>

std::vector<int> encode(std::vector<int> colors);
std::string decode(std::vector<int> message, int a, int b);

#endif

2. 앞 단계 스켈레톤 (encode.cpp)

모든 방의 색을 받아 쪽지가 될 정수 배열을 만들어 돌려주는 함수입니다. 넘겨받는 colors는 1번 방부터 $N$번 방까지의 색을 담고 있어 colors[room]이 곧 그 방의 색이며, 여기서 반환한 배열이 그대로 뒤 단계로 전달됩니다. 쪽지의 맨 앞에는 방의 개수를 적어 두고, 그 뒤로 방마다 번호와 색을 묶은 수를 차례로 이어 붙입니다.

#include "twostep.h"

using namespace std;

vector<int> encode(vector<int> colors) {
    vector<int> message;
    int n = (int)colors.size() - 1;
    message.push_back(n);
    for (int room = 1; room <= n; ++room) {
        message.push_back(room * 10 + colors[room]);
    }
    return message;
}

3. 뒤 단계 스켈레톤 (decode.cpp)

앞 단계가 건넨 message와 비교할 두 방 번호만 받아, 결과 문자열을 돌려주는 함수입니다. 쪽지에 적힌 수들을 다시 번호와 색으로 풀어 각 방의 색을 복원한 뒤, $A$번과 $B$번 방의 색을 맞대어 봅니다.

#include "twostep.h"

using namespace std;

string decode(vector<int> message, int a, int b) {
    int n = message[0];
    vector<int> color(n + 1);
    for (int i = 1; i < (int)message.size(); ++i) {
        int envelope = message[i];
        int room = envelope / 10;
        int room_color = envelope % 10;
        if (1 <= room && room <= n) {
            color[room] = room_color;
        }
    }

    if (color[a] != color[b]) {
        return "different";
    }
    return "same";
}

4. 채점기 (grader.cpp)

main을 품은 파일로, 두 단계를 한자리에서 이어 줍니다. 표준 입력에서 방의 개수와 색, 그리고 비교할 두 방 번호를 읽어들인 뒤 encode를 불러 쪽지를 받고, 쪽지의 순서를 섞은 다음 decode에 넘깁니다. 두 단계가 변수가 아니라 오직 쪽지(message)만으로 이어진다는 사실이 코드에 고스란히 드러납니다.

#include "twostep.h"

#include <iostream>
#include <utility>
#include <vector>
using namespace std;

void shuffle_payload(vector<int>& message) {
    for (int i = (int)message.size() - 1; i > 1; --i) {
        int j = 1 + (i * 37 + 17) % i;
        swap(message[i], message[j]);
    }
}

int main() {
    int n;
    cin >> n;

    vector<int> colors(n + 1);
    for (int room = 1; room <= n; ++room) {
        cin >> colors[room];
    }

    int a, b;
    cin >> a >> b;

    vector<int> message = encode(colors);
    shuffle_payload(message);

    cout << "message";
    for (int value : message) {
        cout << ' ' << value;
    }
    cout << '\n';

    cout << decode(message, a, b) << '\n';
    return 0;
}

5. 예제 입출력 파일 (input.txt, expected.txt)

로컬에서 채점기를 돌려 보고 결과를 맞춰 볼 수 있도록 예제 입출력이 함께 들어 있습니다. 입력은 방의 개수, 각 방의 색, 그리고 비교할 두 방 번호 순으로 적혀 있습니다.

input.txt:

4
1 2 3 1
2 4

expected.txt:

message 4 11 41 33 22
different

이 예제에서 encode는 네 방의 색 [1, 2, 3, 1]을 훑어 [4, 11, 22, 33, 41]이라는 쪽지를 만듭니다. 채점기는 방 정보의 순서를 섞어 [4, 11, 41, 33, 22]를 decode에 넘깁니다. 뒤이어 decode는 이 쪽지만으로 2번 방의 색이 2, 4번 방의 색이 1임을 되살려 내고, 둘이 다르므로 different를 돌려줍니다.

중간 메시지와 채점

서버는 여러 테스트 케이스로 코드를 채점하며, 각 케이스마다 encode와 decode를 차례로 불러 봅니다. decode가 주어진 질문에 모두 옳게 답해야 그 케이스를 통과합니다.

여러 케이스를 묶어 서브태스크(Subtask)를 짓는 방식은 Batch 문제와 같습니다. 한 가지 다른 점은, Two-step 문제는 쪽지의 크기에 상한을 두고 더 짧은 쪽지로 풀어낼수록 높은 점수를 얹어 주는 경우가 많다는 것입니다. 위 예시처럼 모든 방의 정보를 곧이곧대로 늘어놓으면 쪽지가 길어지므로, 만점을 노린다면 정말 필요한 정보만 더 알뜰하게 담아내는 인코딩을 고민해야 합니다.

컴파일 및 실행 방법

두 단계의 스켈레톤 코드와 채점기 파일을 함께 컴파일해야 합니다. main은 grader.cpp 안에 들어 있으며, 컴파일 명령어는 다음과 같습니다.

g++ grader.cpp encode.cpp decode.cpp -std=gnu++20 -O2 -pipe -Wall -o twostep

컴파일이 완료되면 실행 파일(twostep)이 생성됩니다. 생성된 프로그램에 예제 입력 파일(input.txt)을 리다이렉션하여 결과를 확인합니다. 아래와 같이 실행하면 채점기가 입력을 읽어 encode로 쪽지를 만들고, 순서를 섞은 뒤 그 쪽지를 다시 decode에 넘겨 두 단계를 이어 줍니다. 화면에 출력된 내용이 expected.txt의 내용과 일치하는지 비교하여 올바르게 구현했는지 확인할 수 있습니다.

./twostep < input.txt
message 4 11 41 33 22
different

참고로, 제공되는 grader.cpp는 로컬 테스트 용도이므로 두 단계를 잇는 과정에서 중간 쪽지를 출력해 보는 등 디버깅을 위해 코드를 약간 손보아 실행할 수 있습니다. 단, 실제 채점 서버에서는 원본 채점기가 사용된다는 점에 주의해야 합니다.