BOJ 13134 Baseball Watching

이 문제는 백준 온라인 저지 블로그에 풀이가 올라왔지만, 나는 풀이를 보고도 이해를 못했는데, 스터디 그룹의 한 분이 풀이를 알려주셨다. 그래서 풀이는 이해했지만, 막상 구현하려니 쉽지는 않아서 조금 전에 겨우 AC를 받았다.

일단 이 문제는 간단히 설명하면, 야구경기를 보는 동안 각 학생들은 한 회에(총 9회경기) 1, 2, 3번 자리 중  한 자리를 선택해서 앉을 수 있고, 선생님 역시 마찬가지이다.
학생들의 수와 각 학생 별로 앉는 자리가 9개의 수로 주어질 때, 선생님에게 야구 경기가 끝날 때까지 한 번도 걸리지 않는 학생 수의 최소값과 최대값을 구하는 문제이다.

N제한은 무려 30만...
하지만 이 문제의 시간 복잡도는 6의 9제곱이다. O(6^9)
물론, N이 크면 입력받고 문제를 풀기위한 전처리(?)작업을 할 때, 조금 더 시간이 걸리겠지만 6의 9제곱은 천만이 좀 넘어서 30만인 N은 무시되는 것 같다.

핵심만 설명하면, 일단 선생님이 야구장에 앉으실 수 있는 경우의 수는 3의 9제곱이다. 그 3의 9제곱의 각각의 경우에 대하여 학생들이 선생님한테 걸리지 않을 경우의 수는 2의 9제곱이 될 것이다! 이것이 핵심! 그 2의 9제곱의 경우에 대하여 몇 명의 학생이 걸리지 않는지 O(1)만에 구해서 그 중 최소, 최대를 구하면 된다.

그렇다면 어떻게 몇 명의 학생이 안 걸리는지를 O(1)만에 알 수 있을까?
처음에 입력을 받으면서 미리 작업을 해둬야한다. 일단 앉을 수 있는 자리는 1, 2, 3밖에 없고, 9자리이다. 이 것은 9자리의 3진수로 볼 수 있다. 그리고 이 3진수를 10진수로 변환하면 최대 19683인 정수로 변환이 되고, 또한 유일하다. 앉은 자리가 조금이라도 다르거나 앉은 순서가 다르면 다른 정수로 나올 수 밖에 없다. 그래서 입력을 받으면서 바로 10진수로 변환한 후 그 10진수에 해당하는 학생(즉, 9회 내내 같은 위치에 있는 학생의 수)의 수를 카운트해서 배열에 저장해 놓으면, 아까 위에서 말한 2의 9제곱가지 경우또한 10진수 정수로 변환해서 그에 해당하는 안 걸리고 살아남는 학생의 수를 바로 알 수 있다.

구현할 때 좀 어려운 점은, 3의 9제곱에 대한 2의 9제곱가지 경우들을 구현하는 것인데... 재귀로 구현하는 것이 제일 나은 듯하다. 고수님들은 재귀 함수 하나로 구현하셨는데, 잘 이해는 안되고, 일단 나는 재귀 함수 2개를 써서 하나로는 3의 9제곱 가지 경우의 수를 만들고 또 그 안에서 재귀함수2를 호출한다. 그럼 그 재귀함수2는 3의 9제곱 가지 경우의 수 각각에 대하여 2의 9제곱 가지 경우의 수를 만들고, 살아남는 학생의 수를 계산한다.
전역변수를 써서 그나마 큰 어려움 없이 구현했다.

그리고 마지막으로 내가 실수했던 것이 입력받은 값이나, 구한 경우의 수들을 10진수로 변환하는 것이었는데, 3진수를 10진수로 변환할 때는 3의 n제곱을 곱해주고 더해야하는데, 나는 그냥 a의 n제곱을 바로 더하는 식으로 해서 완전 엉터리로 했었다..
그리고 고수분들의 코드를 보니 나처럼 직접 3의 n제곱을 그 때 그 때 계산해서 곱하는 것이 아니라 미리 배열에 넣어놓고 곱하시거나, 아니면 sum=sum*3+a-1  이런 식으로 3이 곱이 누적되어 자연스레 8번, 7번, 6번... 각 자리의 수에 곱해지도록 구현하셨다.
나도 저렇게 구현하여 다시 제출해봐야겠다.

그리고 아직도 이 문제를 완벽히 이해했다고는 볼 수 없지만, 일단 이 문제에서의 핵심은 3의 9제곱에 해당하는 선생님의 경우의 수와 직접 비교할 경우, 하나도 안 걸리는 학생을 찾는 것이므로 9자리를 일일이 비교해야하는 등 복잡해지고, 시간도 많이 걸릴 거 같은데,
그 선생님의 경우의 수에 대해서 학생이 하나도 안 걸리는 경우의 수를 도출해내고, 각 경우의 수를 10진수 정수로 변환하여 비교를 쉽게하고 학생의 수를 쉽게 구할 수 있도록 한 것이다.

꽤 이해하기 어려우면서도 멋있는 문제 같다...