[14524] COWBASIC

마지막 수정 시각: 2021-04-18 14:14:12

문제 링크

풀고 싶다 생각하고 한참 북마크에 넣어뒀다가 엊그제 갑자기 아이디어가 생각나서 풀었다. 처음 문제를 볼 때 막막했던 느낌과 다르게 막상 아이디어를 떠올리고 보니 어렵지 않게 풀 수 있었는데, 풀이 과정이 재밌었고 다른 문제랑 조금 다른 느낌이 드는 부분이 있어서 풀이를 간단히 정리해 봄.

풀이

가장 간단한 풀이부터 생각해보자. 주어진 문법대로 코드를 읽어서 실행하는 인터프리터를 구현하면 원하는 답을 구할 수 있다.

문제가 되는 부분은 반복문이 들어가 있는 부분이다. 반복문을 여러 번 중첩할 수 있고, 두번째 예제만 해도 \( 10^{10} \) 번 명령어를 실행해야 하기 때문에 단순한 인터프리터를 구현하는 것만으로는 시간 초과가 나게 된다.

그러면 이 부분을 어떻게 해야 최적화할 수 있을지 생각해보자.

먼저 변수의 값을 바꾸는 명령어(<variable> = <expression>)를 하나의 함수로 정의한다. 즉, 각 명령어는 명령어를 수행하기 전 프로그램의 상태 \( S \)를 받아서, variable의 값을 expression의 결과로 덧씌운 새로운 상태 \( S' \)을 반환하는 함수가 되는 것이다.

이렇게 생각하면, 순서대로 명령어를 실행하는 것은 명령어를 시작하기 전 상태에 각 명령어에 대응되는 함수를 순차적으로 적용해서 새로운 상태를 만들어내는 과정으로 생각할 수 있다.

즉, 각 명령어에 대응되는 함수가 \( f \), \( g \), \( h \)라고 하고 이 세 명령어를 순차적으로 실행하는 경우를 생각해보자. 모든 명령어를 실행한 뒤의 결과는 \( h(g(f(S))) \) 가 되고, 함수 합성의 형태로 나타낸다면 \( (f \circ g \circ h)(S) \)로 표현할 수 있다.

이제 다시 반복문으로 돌아가서 생각해보자. 반복문 안쪽 단락에 나타나는 명령어들을 순서대로 \(f_1, f_2, f_3, \dots, f_n \) 이라고 나타낼 경우, 이 모든 명령어를 수행하는 것을 묶어서 \( f_1 \circ f_2 \circ \dots \circ f_n\) 이라는 하나의 함수로 쓸 수 있다. 이 함수를 \( f \) 라고 하자. 그러면, 내부 명령어를 \( k \) 번 반복하는 반복문의 경우 이 함수를 \(k\)번 적용한 것, 즉 \(f^k\)에 대응됨을 알 수 있다.

이 때 거듭제곱의 경우 \( f^k = (f^{(\frac{k}{2})})^2 \) 이라는 등식을 이용해서 분할 정복을 통해 \( O(log K) \) 시간에 구할 수 있다. 즉, 주어진 명령어에 대응되는 함수를 정의하는 방법과 임의의 두 함수가 주어졌을 때 둘을 합성한 새로운 함수를 정의하는 방법만 찾아낼 경우 위 방법을 이용해서 프로그램을 충분히 빠르게 실행할 수 있다는 것이다.

이제 명령어로 돌아가서 생각해보자. 문제에 주어진 명령어는 매우 단순한데, 변수의 값을 다른 변수 및 상수의 합으로 바꿔서 대입하는 것 외의 명령어는 존재하지 않는다.

여기서 프로그램에서 정의된 변수가 각각 \( v_1, v_2, v_3, \dots, v_n \)이라고 하자. 이 경우 문제에 주어진 표현식은 항상 \( a_0 + a_1 \cdot v_1 + a_2 \cdot v_2 + \dots + a_n \cdot v_n \) 꼴로 표현할 수 있다. 표현식은 덧셈의 형태로만 나타나고, 같은 변수를 여러번 더하는 것은 그 변수를 더한 횟수(\(a_i\))만큼 곱해서 더하는 것으로 생각할 수 있기 때문이다.

이 때 프로그램에 정의된 변수의 목록은 고정이므로, 계수에 해당하는 부분만 떼어내면 각 명령어에 대응되는 함수를 만들 수 있다. 즉, \( a_0, a_1, \dots, a_n \)을 나열한 것이 각 명령어에 대응되는 함수가 되는 것이다.

이렇게 함수를 정의하고 나면 두 함수를 하나로 합성하는 과정은 정의하기 어렵지 않다.

어떤 함수 \( f \)에 대해, \( f \)를 수행하기 전 각 변수 값의 목록을 \( s_1, s_2, \dots, s_n \)이라고 하고, \( f \)를 수행하고 난 이후 각 변수 값의 목록(명령어를 수행하고 난 이후의 상태)을 \(t_1, t_2, \dots, t_n\) 이라고 하자. 함수 \( f \)는 각각의 변수 \( t_i \)에 대해, \( t_i = a_0 + a_1 \cdot s_1 + \dots + a_n \cdot s_n\) 으로 정의됨을 나타내는 계수 수열 \(a\) 의 집합으로 표현할 수 있다.

똑같은 방식으로 함수 \( f \)에 이어 함수 \( g \)를 적용하는 경우를 생각해보자. \( g \)를 적용한 이후 각 변수가 가지게 되는 상태 값을 \(u_1, u_2, \dots, u_n\)이라고 하고 하고 다시 함수 \( g \)에 대응되는 계수 수열을 \(b\)라고 쓰면, \(u_i = b_0 + b_1 \cdot t_1 + b_2 \cdot t_2 + \dots b_n \cdot t_n \)으로 표현할 수 있다. 이 때, \( t_i \)를 다시 풀어쓰면 \( t_i = a_0 + a_1 \cdot s_1 + \dots + a_n \cdot s_n\) 의 꼴이 되므로 이 식을 풀어써서 두 함수를 합성했을 때 각 변수에 대응되는 계수값을 계산할 수 있다. 이 과정을 잘 정리해보면, 이러한 곱셈과 덧셈 과정이 행렬 곱으로 유도됨을 알 수 있다.

그러면 각 함수는 하나의 행렬, 함수 합성은 행렬 곱으로 표현할 수 있으므로 함수를 합성하는 과정의 시간복잡도는 변수 개수를 \(V\)라고 했을 때 \(O(V^3)\)이 됨을 알 수 있다. 행렬 곱의 거듭 제곱은 \(O(logK)\) 만큼의 시간이 걸리므로, 가능한 최대 변수 개수를 \(V\), 가능한 반복문 루프 횟수의 최대를 \(K\)라고 하면 주어진 문제를 \(O(V^3logK)\) 시간에 해결할 수 있음을 알 수 있다. 프로그램의 라인 수가 최대 100줄이라고 했으므로 충분히 시간 안에 수행 가능한 시간 복잡도가 된다.

이 때, 행렬에서 대부분의 값이 0으로 구성된다는 점을 이용해서 실제 계수가 있는 부분만 계산하게끔 만들어주면 좀 더 빠르게 동작하게 만들 수 있으나 문제를 해결하는 과정에서 필요한 부분은 아니다.