[백준][C++] 3954: Brainf**k 인터프리터

문제 링크: https://www.acmicpc.net/problem/3954

 

구현 문제입니다.

문제의 조건을 보면 테스트케이스가 20개 이하고, 각 테스트케이스에서 5000만번의 O(1) 연산이 발생되기 때문에, 보통 1억에 1초라고 하니까 20*5천만=10억=10초 > 7초 라는 계산을 해서 뭔가 규칙을 찾아내야될 것 같은 문제처럼 보입니다.

근데 그냥 문제 조건대로 돌려보면 됩니다... 1시간동안 곰곰이 생각해봤지만 돌려보지 않으면 무한 루프를 찾을 수 없을 것 같습니다. 언제나처럼 증명은 못합니다. 그냥 그럴 것 같아요.

 

어쨌거나 그냥 문제에 있는대로 돌려보면 됩니다

 

주의할 사항이 있습니다.

• 문제에 주어진대로 배열에 unsigned 8bit 정수를 쓰거나, 안그러면 mod 256을 잘 해줘야 합니다.
  C++이면 그냥 uint8_t 쓰는게 편합니다
• 무한루프의 범위를 잘 검사해야 합니다

 

무한루프에 빠졌을 때, 어떤 무한루프를 출력해야하는지가 좀 까다롭습니다.

저는 지금까지 방문한 괄호중에 가장 바깥 괄호를 가져오는 식으로 풀었습니다.

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;


map<int, int> bracket_LR, bracket_RL;	// [, ] idx
const int MAX_TURN = 50'000'000;

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);


	int t;
	cin >> t;
	while (t--) {
		int sm, sc, si;
		cin >> sm >> sc >> si;

		string program;
		cin >> program;

		string input;
		cin >> input;

		vector<uint8_t> arr(sm);

		// 괄호 좌우 저장
		bracket_LR.clear();
		bracket_RL.clear();
		stack<int> left_bracket_idx;
		for (int i = 0; i < program.size(); ++i) {
			if (program[i] == '[') {
				left_bracket_idx.push(i);
			}
			else if (program[i] == ']') {
				int left_idx = left_bracket_idx.top();
				left_bracket_idx.pop();
				bracket_LR[left_idx] = i;
				bracket_RL[i] = left_idx;
			}
		}


		int program_idx = 0;
		int input_idx = 0;
		int ptr = 0;

		bool loop = true;

		int max_program_idx = 0;

		for (int turn = 0;
			turn < MAX_TURN;
			++turn) {
			max_program_idx = max(max_program_idx, program_idx);

			if (program_idx == sc) {
				loop = false;
				break;
			}

			switch (program[program_idx]) {
			case '-':
				--arr[ptr];
				break;

			case '+':
				++arr[ptr];
				break;

			case '<':
				ptr = (ptr - 1 + sm) % sm;
				break;

			case '>':
				ptr = (ptr + 1) % sm;
				break;

			case '[':
				if (arr[ptr] == 0) {
					// jump
					program_idx = bracket_LR[program_idx];
				}
				break;

			case ']':
				if (arr[ptr] != 0) {
					// jump
					program_idx = bracket_RL[program_idx];
				}
				break;

			case '.':
				// print
				break;

			case ',':
				int c = (input_idx < si ? static_cast<uint8_t>(input[input_idx++]) : 255);
				arr[ptr] = c;
				break;
			} // switch

			++program_idx;
		} // for

		if (loop) {
			// 지금까지 방문한 괄호 중에 가장 바깥 괄호 가져옴
			auto RL = bracket_RL.upper_bound(max_program_idx);
			--RL;
			cout << "Loops " << RL->second << ' ' << RL->first << '\n';
		}
		else {
			cout << "Terminates\n";
		}
	}

	

	return 0;
}