RiseOJ는 solved.ac와 제휴 관계가 없습니다. 티어 아이콘 © solved.ac. solved.ac
포럼
A00004

알파카컵 1회: D - 코딩 천재 알파카

Gold I 골드 I
난이도
1s
시간 제한
1024MB
메모리 제한
6
맞았습니다!!
50
제출 수
12.0%
정답률
레이팅

의견: 0

설명

알파카는 천재라서 Brainfuck으로 무엇이든 짤 수 있다. 하지만 자신이 짠 코드가 무엇을 출력하는지는 모른다. 주어진 Brainfuck 프로그램을 실행하면 무엇이 출력되는지 구해 보자.

명령어
- > : 포인터를 오른쪽으로 한 칸 이동
- < : 포인터를 왼쪽으로 한 칸 이동
- + : 현재 셀의 값을 \(1\) 증가
- - : 현재 셀의 값을 \(1\) 감소
- . : 현재 셀의 값을 아스키 문자로 출력
- [ : 현재 셀의 값이 \(0\)이면 짝이 맞는 ] 다음으로 점프
- ] : 현재 셀의 값이 \(0\)이 아니면 짝이 맞는 [로 점프

제약

프로그램의 명령어 개수 \(\le 1{,}000{,}000\). 메모리는 \(30{,}000\)개의 셀로 이루어지며, 각 셀은 \(0\) 이상 \(255\) 이하의 정수를 담는다(\(255\)에서 \(1\)을 더하면 \(0\), \(0\)에서 \(1\)을 빼면 \(255\)로 wrap-around). 포인터는 \(0\)번 셀에서 시작하고 모든 셀은 \(0\)으로 초기화되어 있다.

입력 형식

하나의 Brainfuck 프로그램이 주어진다(여러 줄에 걸쳐 주어질 수 있다). 사용되는 명령어는 > < + - . [ ] 뿐이며, 입력 명령어 ,(콤마)는 주어지지 않는다. 명령어가 아닌 문자는 무시한다.

출력 형식

프로그램을 실행했을 때 출력되는 내용을 그대로 출력한다. 단, 다음 두 경우에는 아무것도 출력하지 않고 \(-1\)만 출력한다.
1. 프로그램에 문법 오류가 있어 실행할 수 없는 경우([와 ]의 짝이 맞지 않는 경우).
2. 프로그램이 무한 루프에 빠지는 경우. 프로그램이 명령을 \(10{,}000{,}000\)번 실행하고도 종료되지 않으면 무한 루프로 간주한다.

서브태스크
서브태스크점수설명

Subtask 1

65점

정상 동작 (출력 있음)

Subtask 2

15점

정상 동작 (출력 없음)

Subtask 3

10점

문법 오류 → -1

Subtask 4

10점

무한 루프 → -1

예제 1
입력
++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
출력
Hello World!
예제 2
입력
+++++++++[>+++++++<-]>++.
출력
A
예제 3
입력
+++[>++<-
출력
-1
예제 4
입력
+[]
출력
-1
문제 정보

joomongogo 작성

출처 알파카컵 1회

대회 > 알파카컵 > 알파카컵 1회
태그
#파싱 JudgeOriginal

해설

알파카컵 1회: D - 코딩 천재 알파카

알파카컵 1회: D - 코딩 천재 알파카

1. 문제 요약

하나의 Brainfuck 프로그램이 주어지면, 그 프로그램을 실행했을 때 출력되는 내용을 그대로 구하는 문제입니다. 사용되는 명령어는 >, <, +, -, ., [, ] 일곱 가지이며 입력 명령어 ,는 등장하지 않고, 명령어가 아닌 문자는 모두 무시합니다.

메모리는 \(30,000\)개의 셀로 이루어지며 각 셀은 \(0\)부터 \(255\)까지의 값을 가집니다(\(255\)에서 \(1\)을 더하면 \(0\), \(0\)에서 \(1\)을 빼면 \(255\)로 wrap-around). 포인터는 \(0\)번 셀에서 시작하고 모든 셀은 \(0\)으로 초기화되어 있습니다. 단, 다음 두 경우에는 출력 대신 \(-1\)만 출력해야 합니다.
- [와 ]의 짝이 맞지 않는 문법 오류가 있는 경우.
- 프로그램이 명령을 \(10,000,000\)번 실행하고도 종료되지 않는 무한 루프의 경우.

서브태스크는 입력의 크기가 아니라 프로그램이 어떤 거동을 보이는지(출력 유무, 문법 오류, 무한 루프)로 나뉩니다. 핵심은 이 네 가지 경우를 모두 하나의 견고한 인터프리터로 처리하는 것입니다. 따라서 아래 각 서브태스크에서는 동일한 인터프리터가 해당 경우를 어떻게 다루는지에 초점을 두어 설명합니다.

2. [서브태스크 1]: 정상 동작 (출력 있음)

가장 기본이 되는, 문법이 올바르고 정상적으로 종료되며 . 명령으로 무언가를 출력하는 경우입니다. 인터프리터의 실행 엔진 자체를 정확히 구현하는 것이 이 서브태스크의 목표입니다.

  • 풀이: 먼저 입력에서 명령어 일곱 가지만 골라 명령어 스트림 code로 만듭니다(명령어가 아닌 문자는 이 단계에서 버립니다). 포인터 ptr은 \(0\)에서 시작하고, 셀 배열 mem은 unsigned char로 잡아 자동으로 \(0\)~\(255\) wrap-around가 되게 합니다. 프로그램 카운터 pc를 \(0\)부터 진행시키며 명령어를 하나씩 해석합니다. >/<는 포인터를 좌우로 옮기고, +/-는 현재 셀 값을 증감하며, .는 현재 셀 값을 아스키 문자로 출력 버퍼에 담습니다. [/]는 다음 서브태스크에서 설명할 점프 테이블을 이용해 분기합니다. 모든 명령이 끝나면 누적한 출력 버퍼를 그대로 출력합니다.

  • 시간 복잡도: 실제로 실행되는 명령 수를 \(E\)라 하면 인터프리터는 \(O(E)\)에 동작합니다. 실행 명령 수의 상한이 \(10^7\)이므로 충분히 빠릅니다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll LIMIT = 10000000;
const ll CELLS = 30000;
int main() {
    fastio
    // 입력 프로그램은 여러 줄에 걸쳐 주어질 수 있으므로 전부 읽어들인다.
    string line, src = "";
    while (getline(cin, line)) src += line;
    // 명령어 일곱 가지만 추려 명령어 스트림을 만든다(나머지는 무시).
    string code = "";
    for (char ch : src) {
        if (ch == '>' || ch == '<' || ch == '+' || ch == '-' ||
            ch == '.' || ch == '[' || ch == ']') code += ch;
    }
    ll len = (ll)code.size();
    // (이 서브태스크에서는 문법이 올바르므로 점프 테이블이 항상 정상적으로 만들어진다.)
    vector<ll> jump(len);
    stack<ll> st;
    for (ll i = 0; i < len; i++) {
        if (code[i] == '[') st.push(i);
        else if (code[i] == ']') { ll j = st.top(); st.pop(); jump[i] = j; jump[j] = i; }
    }
    vector<unsigned char> mem(CELLS, 0); // unsigned char 로 0~255 wrap-around 자동 처리
    ll ptr = 0, pc = 0;
    string out = "";
    while (pc < len) {
        char c = code[pc];
        if (c == '>') ptr++;
        else if (c == '<') ptr--;
        else if (c == '+') mem[ptr]++;
        else if (c == '-') mem[ptr]--;
        else if (c == '.') out += (char)mem[ptr];
        else if (c == '[') { if (mem[ptr] == 0) pc = jump[pc]; }
        else if (c == ']') { if (mem[ptr] != 0) pc = jump[pc]; }
        pc++;
    }
    cout << out;
    return 0;
}

3. [서브태스크 2]: 정상 동작 (출력 없음)

문법이 올바르고 정상적으로 종료되지만 . 명령이 단 한 번도 실행되지 않아 아무것도 출력하지 않는 경우입니다. 예를 들어 셀 값을 잔뜩 계산하기만 하고 출력하지 않는 프로그램이 여기에 해당합니다.

  • 풀이: 서브태스크 1의 인터프리터를 그대로 사용하면 됩니다. 핵심은 출력 버퍼를 빈 문자열로 초기화해 두고, . 명령이 실행될 때만 문자를 덧붙이는 구조입니다. .이 한 번도 등장하지 않거나 실행되지 않으면 버퍼는 끝까지 비어 있으므로, 마지막에 그대로 출력하면 자연스럽게 아무것도 출력하지 않게 됩니다. 즉 출력 유무를 위해 별도의 분기를 둘 필요가 전혀 없고, 정상 종료라면 누적 버퍼를 출력하기만 하면 됩니다. -1을 내보내야 하는 경우와 혼동하지 않도록, "출력이 없는 정상 종료"와 "오류로 인한 \(-1\)"을 명확히 구분하는 것이 중요합니다.

  • 시간 복잡도: 마찬가지로 실행 명령 수 \(E\)에 대해 \(O(E)\)입니다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll LIMIT = 10000000;
const ll CELLS = 30000;
int main() {
    fastio
    string line, src = "";
    while (getline(cin, line)) src += line;
    string code = "";
    for (char ch : src) {
        if (ch == '>' || ch == '<' || ch == '+' || ch == '-' ||
            ch == '.' || ch == '[' || ch == ']') code += ch;
    }
    ll len = (ll)code.size();
    vector<ll> jump(len);
    stack<ll> st;
    for (ll i = 0; i < len; i++) {
        if (code[i] == '[') st.push(i);
        else if (code[i] == ']') { ll j = st.top(); st.pop(); jump[i] = j; jump[j] = i; }
    }
    vector<unsigned char> mem(CELLS, 0);
    ll ptr = 0, pc = 0;
    string out = ""; // 빈 채로 시작 → '.' 이 안 실행되면 끝까지 비어 있다.
    while (pc < len) {
        char c = code[pc];
        if (c == '>') ptr++;
        else if (c == '<') ptr--;
        else if (c == '+') mem[ptr]++;
        else if (c == '-') mem[ptr]--;
        else if (c == '.') out += (char)mem[ptr]; // 여기서만 출력이 쌓인다.
        else if (c == '[') { if (mem[ptr] == 0) pc = jump[pc]; }
        else if (c == ']') { if (mem[ptr] != 0) pc = jump[pc]; }
        pc++;
    }
    cout << out; // 비어 있으면 아무것도 출력되지 않는다.
    return 0;
}

4. [서브태스크 3]: 문법 오류 → -1

[와 ]의 짝이 맞지 않아 실행 자체가 불가능한 경우입니다. 예를 들어 +++[>++<- 처럼 ]가 부족하거나, 반대로 여는 괄호 없이 ]가 먼저 나오는 경우입니다. 이때는 프로그램을 실행하지 않고 곧바로 \(-1\)만 출력해야 합니다.

  • 풀이: 인터프리터를 돌리기 전에 점프 테이블을 만드는 과정에서 짝 맞춤 여부를 검사합니다. 스택을 두고 명령어 스트림을 왼쪽부터 훑으며, [를 만나면 그 위치를 스택에 넣고, ]를 만나면 스택에서 하나를 꺼내 서로의 점프 대상으로 연결합니다. 이때 두 가지 불균형을 잡아내야 합니다. (1) ]를 만났는데 스택이 비어 있으면 짝이 없는 닫는 괄호이므로 오류입니다. (2) 스트림을 모두 훑은 뒤에도 스택이 비어 있지 않으면 짝이 없는 여는 괄호가 남은 것이므로 오류입니다. 둘 중 하나라도 발생하면 메모리/포인터를 건드리지 않고 즉시 -1을 출력하고 종료합니다.

  • 시간 복잡도: 명령어 개수 \(L\)에 대해 점프 테이블 구성과 검사는 한 번의 선형 스캔이므로 \(O(L)\)입니다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll LIMIT = 10000000;
const ll CELLS = 30000;
int main() {
    fastio
    string line, src = "";
    while (getline(cin, line)) src += line;
    string code = "";
    for (char ch : src) {
        if (ch == '>' || ch == '<' || ch == '+' || ch == '-' ||
            ch == '.' || ch == '[' || ch == ']') code += ch;
    }
    ll len = (ll)code.size();
    vector<ll> jump(len);
    stack<ll> st;
    bool ok = true;
    for (ll i = 0; i < len; i++) {
        if (code[i] == '[') st.push(i);
        else if (code[i] == ']') {
            if (st.empty()) { ok = false; break; } // 짝 없는 ']'
            ll j = st.top(); st.pop();
            jump[i] = j; jump[j] = i;
        }
    }
    // 짝 없는 ']' 가 있었거나, 닫히지 않은 '[' 가 남았으면 문법 오류.
    if (!ok || !st.empty()) {
        cout << -1; // 실행하지 않고 즉시 종료
        return 0;
    }
    vector<unsigned char> mem(CELLS, 0);
    ll ptr = 0, pc = 0;
    string out = "";
    while (pc < len) {
        char c = code[pc];
        if (c == '>') ptr++;
        else if (c == '<') ptr--;
        else if (c == '+') mem[ptr]++;
        else if (c == '-') mem[ptr]--;
        else if (c == '.') out += (char)mem[ptr];
        else if (c == '[') { if (mem[ptr] == 0) pc = jump[pc]; }
        else if (c == ']') { if (mem[ptr] != 0) pc = jump[pc]; }
        pc++;
    }
    cout << out;
    return 0;
}

5. [서브태스크 4]: 무한 루프 → -1

문법은 올바르지만 영원히 종료되지 않는 경우입니다. 예를 들어 +[]는 현재 셀이 항상 \(1\)이라 루프를 빠져나갈 수 없습니다. 이런 프로그램은 무한히 실행되므로, 정지 여부를 미리 판별할 수는 없고(정지 문제) 대신 실행 횟수에 상한을 두어 처리합니다.

  • 풀이: 실제로 실행되는 명령의 개수를 세는 카운터 steps를 두고, 명령을 하나 해석할 때마다 \(1\)씩 증가시킵니다. 이 값이 \(10,000,000\)을 초과하면 무한 루프로 간주하고 루프를 빠져나와 -1만 출력합니다. 주의할 점은 무시되는 문자나 점프로 건너뛰는 명령이 아니라 실제로 처리되는 명령 하나하나를 세야 한다는 것입니다([/]의 분기 판정도 하나의 실행으로 셉니다). 이 한도 검사를 실행 루프 맨 앞에 두면, 정상 종료 프로그램은 한도에 닿기 전에 끝나서 정상 출력을 내고, 무한 루프 프로그램만 한도에서 걸려 -1을 내게 됩니다.

  • 시간 복잡도: 실행 명령 수가 한도 \(L_{\max}=10^7\)로 제한되므로 최악의 경우에도 \(O(L_{\max})\)에 종료가 보장됩니다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll LIMIT = 10000000;
const ll CELLS = 30000;
int main() {
    fastio
    string line, src = "";
    while (getline(cin, line)) src += line;
    string code = "";
    for (char ch : src) {
        if (ch == '>' || ch == '<' || ch == '+' || ch == '-' ||
            ch == '.' || ch == '[' || ch == ']') code += ch;
    }
    ll len = (ll)code.size();
    vector<ll> jump(len);
    stack<ll> st;
    bool ok = true;
    for (ll i = 0; i < len; i++) {
        if (code[i] == '[') st.push(i);
        else if (code[i] == ']') {
            if (st.empty()) { ok = false; break; }
            ll j = st.top(); st.pop();
            jump[i] = j; jump[j] = i;
        }
    }
    if (!ok || !st.empty()) { cout << -1; return 0; }
    vector<unsigned char> mem(CELLS, 0);
    ll ptr = 0, pc = 0, steps = 0;
    string out = "";
    bool infinite = false;
    while (pc < len) {
        if (steps > LIMIT) { infinite = true; break; } // 1e7 초과 → 무한 루프 간주
        steps++; // 실제로 실행되는 명령만 센다.
        char c = code[pc];
        if (c == '>') ptr++;
        else if (c == '<') ptr--;
        else if (c == '+') mem[ptr]++;
        else if (c == '-') mem[ptr]--;
        else if (c == '.') out += (char)mem[ptr];
        else if (c == '[') { if (mem[ptr] == 0) pc = jump[pc]; }
        else if (c == ']') { if (mem[ptr] != 0) pc = jump[pc]; }
        pc++;
    }
    if (infinite) { cout << -1; return 0; } // 누적 출력은 버리고 -1 만 출력
    cout << out;
    return 0;
}

6. 정해

네 가지 경우를 모두 처리하는 완전하고 견고한 Brainfuck 인터프리터입니다.

  • 풀이: 동작 순서는 다음과 같습니다. ① 입력 프로그램을 여러 줄에 걸쳐 주어질 수 있음을 고려해 끝까지 읽은 뒤, 일곱 가지 명령어만 추려 명령어 스트림을 만듭니다(나머지 문자는 무시). ② 스택으로 한 번 스캔하며 [/]의 짝 맞춤을 검사하고, 동시에 서로를 가리키는 점프 테이블을 구성합니다. 이때 짝 없는 ](스택이 빔)나 닫히지 않은 [(스캔 후 스택에 잔여)가 발견되면 곧바로 -1을 출력하고 종료합니다. ③ 포인터를 \(0\), 셀 배열을 모두 \(0\)으로 초기화한 뒤 명령어 스트림을 해석합니다. 셀은 unsigned char로 두어 \(0\)~\(255\) wrap-around가 자동으로 처리되게 합니다. ④ 실행되는 명령마다 steps를 증가시켜 \(10^7\)을 초과하면 무한 루프로 보고 출력을 버린 채 -1만 출력합니다. ⑤ 정상적으로 종료되면 누적한 출력 버퍼를 그대로 내보냅니다. 점프 테이블을 미리 구성해 두므로 루프 진입/탈출 시 괄호를 다시 찾아 헤맬 필요 없이 \(O(1)\)에 분기할 수 있습니다.

  • 시간 복잡도: 명령어 개수 \(L\)에 대한 전처리(스트림 구성·점프 테이블)가 \(O(L)\), 실행은 실제 실행 명령 수 \(E \le 10^7\)에 대해 \(O(E)\)입니다. 따라서 전체 시간 복잡도는 \(O(L + 10^7)\)로 제한 시간 내에 안정적으로 통과합니다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll LIMIT = 10000000; // 무한 루프 판정 기준
const ll CELLS = 30000;    // 메모리 셀 개수
int main() {
    fastio
    // 1) 프로그램 전체 읽기 (여러 줄 가능)
    string line, src = "";
    while (getline(cin, line)) src += line;
    // 2) 명령어가 아닌 문자는 무시하고 명령어 스트림 구성
    string code = "";
    for (char ch : src) {
        if (ch == '>' || ch == '<' || ch == '+' || ch == '-' ||
            ch == '.' || ch == '[' || ch == ']') code += ch;
    }
    ll len = (ll)code.size();
    // 3) 점프 테이블 구성 + 괄호 짝 검사
    vector<ll> jump(len);
    stack<ll> st;
    bool ok = true;
    for (ll i = 0; i < len; i++) {
        if (code[i] == '[') st.push(i);
        else if (code[i] == ']') {
            if (st.empty()) { ok = false; break; } // 짝 없는 ']'
            ll j = st.top(); st.pop();
            jump[i] = j; jump[j] = i;
        }
    }
    if (!ok || !st.empty()) { // 짝 없는 ']' 또는 닫히지 않은 '['
        cout << -1;
        return 0;
    }
    // 4) 실행
    vector<unsigned char> mem(CELLS, 0); // 0~255 wrap-around 자동
    ll ptr = 0, pc = 0, steps = 0;
    string out = "";
    bool infinite = false;
    while (pc < len) {
        if (steps > LIMIT) { infinite = true; break; } // 1e7 초과 → 무한 루프
        steps++;
        char c = code[pc];
        if (c == '>') ptr++;
        else if (c == '<') ptr--;
        else if (c == '+') mem[ptr]++;
        else if (c == '-') mem[ptr]--;
        else if (c == '.') out += (char)mem[ptr];
        else if (c == '[') { if (mem[ptr] == 0) pc = jump[pc]; }
        else if (c == ']') { if (mem[ptr] != 0) pc = jump[pc]; }
        pc++;
    }
    if (infinite) { // 무한 루프면 출력 버리고 -1 만
        cout << -1;
        return 0;
    }
    // 5) 정상 종료 → 누적 출력 그대로 (출력 없으면 빈 문자열)
    cout << out;
    return 0;
}

평가 및 의견

알파카컵 1회: D - 코딩 천재 알파카

개요
출제자 난이도 Gold I 골드 I 의견 0 / 50 공개 집계 (커뮤니티 난이도, 주요 주제, 품질)는 의견이 충분히 모이면 공개됩니다.

Log in to rate problems.

개별 의견

아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.

풀이 제출

알파카컵 1회: D - 코딩 천재 알파카

게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다. 로그인하고 제출하기
작성 중 Rush? 언어 레퍼런스 읽기 ↗
공개
C++20 Tab 들여쓰기 · Ctrl+/ 주석 토글 · Enter 자동 들여쓰기
행1 열1 1줄 0자 공백: 4 · UTF-8