[BOJ] 19677 Holy cow, Vim! (Hard)

문제 설명

• 생략한다.

문제 접근

이 문제를 풀기 위해서는 굉장히 많은 시행착오를 거쳐야 한다. 아래는 그 시행착오를 줄이기 위한 접근들을 단계별로 서술해놓았다. 그러나 이를 보지 않고 많은 시행착오를 겪는 것이 거의 모든 측면에서 도움이 될 것으로 보인다.

일단 lexicographical하게 정렬했을 때 명령어의 순서는

'*', '+', '-', '/', 'dup', 'input', 'jump', 'pop', 'print', 'push' 순서이다.

문제는 이 중 사칙연산과 dup은 우선순위도 빠르면서 스택에 필수적으로 하나 이상의 원소를 요구하기에, 두 명령어 중 첫 번째 명령어로는 쓰일 수 없다(만약 쓰인다면 정렬되었을 때 맨 위를 차지해서 바로 에러를 띄울 것이다). 그래서 결국 두 명령어 중 첫 명령어로 사용할 수 있는 것은 input, jump, pop, print, push이다.

이 중 input은 프로그램 전체에서 첫 명령어로 두 개 이상 쓰기 곤란하다. 왜냐하면 만약 input을 2개 사용할 경우 정렬되었을 때 입력을 두 개 받게 되는데, 이를 막기 위해서는 첫 input의 두 번째 명령어가 반드시 jump여야 하고 이 선택은 뒤의 과정을 진행하는데 굉장히 많은 애로사항을 만들게 된다. 따라서 input을 하나만 쓰면서 문제를 풀어보려는 노력을 하게 된다.

input을 그러면 어디에 써야 하는가? 를 찾기 위해 많은 시간을 투자해야 한다. 결론만 말하면, input은 프로그램의 맨 마지막 부분에 위치하는 게 편하다. 왜냐하면 필수는 아니지만 프로그램의 원활한 설계를 위해 input 뒤에 명령어를 추가로 붙일 필요가 있기 때문이다. 이 붙여야 하는 명령어는 dup으로, 왜 dup을 붙여야 하는지 지금부터 생각해 보자.

정렬되었을 때 -x를 출력하는 정석적인 프로그램은 다음과 같을 것이다. l1과 l2는 임의로 붙인 라벨 번호이고, :l1과 :l2로 표시하였다. -x를 -1을 곱해서 계산했다면 훨씬 편했겠지만, 나는 멍청했기에 0에서 x를 빼서 계산했다. 이 구조는 노가다로 찾을 수도 있지만, 노가다로 찾는다 하더라도 하나의 관찰이 있어야 한다. 이는 바로 아래 문단에서 'dup'을 예시로 들어 설명한다.

input
jump l1
pop;- :l2
print;jump end
push 0 :l1
push 0;jump l2

입력을 x라고 하자. dup은 x의 제곱을 출력하기 위해 필수적으로 x에 대해 한 번 이상 적용되어야 한다. 만약 x에 dup을 input이 아닌 다른 상황에서 사용한다고 해 보자. 그러려면 스택의 맨 위 원소가 입력이어야 한다. x가 스택의 맨 위에 있으려면 어떻게 해야 할까? dup은 앞서 말했듯이 첫 번째 명령어로 쓰일 수 없으므로, input, jump, pop, print, push 중 하나에 붙어야 한다. 그러나 jump는 뒤 명령어를 무시하고 print는 출력 후 더 이상 할 수 있는 것이 없으므로 input, pop, push 중 하나에 붙어야 한다. 그러나 push를 하면 스택의 위 원소가 바뀌므로 input이나 pop 중 하나에 붙어야 한다. 이는 dup에만 한정되는 것이 아니고, 사칙연산에도 동일하게 적용되는 성질이다. 그러나 input은 단 한 번 밖에 사용할 수 없다. 따라서 일반적으로는 push (쓰레기 값)을 한 후 pop (원하는 연산) 을 하는 형태로 스택의 맨 위 값에 대한 연산을 진행하게 될 것이다.

이 관찰을 토대로 위의 정렬된 기초 코드를 만들 수 있다(빼기 연산을 해야 하므로). 이제 이 정렬된 기초 코드의 구조를 깨트리지 않으면서 순서를 바꾸고 명령어를 추가해 정순과 역순에 대해 올바른 출력이 나오도록 할 것이다.

이 구조를 깨트리지 않으면서 추가하기 쉬운 명령어들은, 프로그램을 바로 종료하는 print;jump end 명령어, 곱셈과 덧셈에 대한 pop;(연산자) 명령어와 push (큰 값) 명령어이다. 잘 보면 이 명령어를 추가해도 위 구조에서는 실행되지 않음을 확인할 수 있다. 다르게 말하면 이 연산자들 말고 다른 연산자들을 활용하기는 상대적으로 꺼려진다는 뜻이다. 이 꺼려지는 명령어에는 pop;dup이 포함된다. 왜냐면 라벨 l2 뒤에 들어가 종료조건으로 가는 것을 방해하기 때문이다. 따라서 dup은 input 뒤에 붙는 것이 정석적이다.

이를 토대로 정렬과 역순에 대해 올바른 답을 낼 것 같은 코드가 완성된다. 이는 input과 기타 명령어 몇 개의 순서를 적절히 바꾸고 껄끄럽지 않은 명령어를 추가함으로서 완성할 수 있다.

jump l1
pop;- :l2
push 0 :l1
push 0;jump l2
print;jump end
pop;*
push Z
input;dup

참고로 정렬했을 때는 다음과 같다.

input;dup
jump l1
pop;*
pop;- :l2
print;jump end
push 0 :l1
push 0;jump l2
push Z

그럼 이제 여기에서 더 나아가 정순에 대한 올바른 답을 출력하는 코드를 만들어야 한다. 정순일 때는 맨 아래의 input을 사용하지 못하므로 새로운 input을 사용해야 한다. 이때 input이 첫 번째 명령어가 될 수는 없으므로 무언가 뒤에 붙어야 되고, 만만한 push 뒤에 붙일 수 있다(정순일 때는 그냥 출력하기만 하면 되므로). 그러면 정순에 대해서도 똑같이 하면 되지 않을까?

push Z;input
print;jump end
jump l1
pop;- :l2
push 0 :l1
push 0;jump l2
print;jump end
pop;*
push Z
input;dup

맨 위에 두 줄을 추가한 위 코드로 정답을 받을 수 있다. 실제 제출한 코드는 다음과 같다.

push 9;input
print;jump 10
jump 6
pop;-
push 0
push 0;jump 3
print;jump 10
pop;*
push 9
input;dup