취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 3287번 문제인 CALC이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/3287 

이 글에서 op는 연산자 문자('#' 또는 '$')를 의미하고, X와 Y는 표현식을 나타내는 문자로 사용하겠다.

주어지는 표현식은 "A", "B"를 제외하면 항상 "(ext op exp)"와 같은 형태로 구성되어 있음을 관찰하자.

위의 관찰을 이용하면, 다음과 같은 세 가지를 할 수 있다면 문제를 충분히 해결할 수 있음을 발견할 수 있다.

(1) 리스트의 끝이 A B와 같이 주어져있을 때 그 위치의 리스트를 A A B로 교체하기

(2) 리스트의 끝이 A B와 같이 주어져있을 때 그 위치의 리스트를 B A B로 교체하기

(3) 리스트의 끝이 X Y A B와 같이 주어져있을 때 그 위치의 리스트를 (X op Y) A B로 교체하기

위 세 가지를 하는 방법의 자세한 설명은 생략하도록 하겠다. 다만 아래의 코드에 가능한 방법중 하나가 나와있으므로 전혀 방법을 못 찾겠다면 참고해보자.

위의 세가지가 가능하다면, 리스트의 끝이 A B와 같이 주어져있을 때 그 위치의 리스트를 X A B로 교체하는 함수 f(X)를 고안해낼 수 있다. 구체적으로 X가 A와 같다면 (1)을, B와 같다면 (2)를, (P op Q)와 같다면 f(P), f(Q) 및 (3)을 순서대로 호출하는 것으로 리스트의 끝이 A B와 같을 때 이를 X A B로 바꿀 수 있다.

이와 같은 함수 f를 이용해 A B를 exp A B로 바꾸고, DROP을 2회 실행해 문제를 해결하자.

위와 같은 방법이 문제의 제약(리스트의 원소의 최대개수가 100, 총 1만번의 연산만 수행 가능)을 만족하는지를 확인하는 것은 간단하므로 서술을 생략한다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

string s;

void func(int L, int R) {
	if (L == R) {
		if (s[L] == 'A') {
			cout << "SWAP\n";
			cout << "DUP\n";
			cout << "DUP\n";
			cout << "ROT\n";
			cout << "ROT\n";
			cout << "DROP\n";
		}
		else {
			cout << "DUP\n";
			cout << "DUP\n";
			cout << "ROT\n";
			cout << "ROT\n";
			cout << "ROT\n";
			cout << "DROP\n";
		}
		return;
	}
	int cnt = 0;
	L++, R--;
	for (int i = L; i <= R; i++) {
		if (s[i] == '(') cnt++;
		else if (s[i] == ')') cnt--;
		else if ((s[i] == '#' || s[i] == '$') && !cnt) {
			func(L, i - 1);
			func(i + 1, R);
			cout << "ROT\n";
			cout << "ROT\n";
			if (s[i] == '#') cout << "HASH\n";
			else cout << "DOLLAR\n";
			cout << "DUP\n";
			cout << "ROT\n";
			cout << "ROT\n";
			cout << "ROT\n";
			cout << "DROP\n";
			return;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> s;
	func(0, s.length() - 1);
	cout << "DROP\n";
	cout << "DROP\n";
}