BOJ 13908 비밀번호

어렵다. 생각이 잘 안난다.
그래서 떠오르는 건 brute force밖에 없다...
일단은 최대 7자리 숫자이기 때문에, 모든 숫자를 다 만들면 1000만 번이 필요하다.
그리고 각 숫자에 대해서 주어진 m개의 숫자를 포함하는지 확인하는데 7번이면 된다.
즉, 모든 경우를 다 해봐도 7천만 번에 다 처리할 수 있다.
해보자. 좀 더 효율적이고 좋은 방법이 있을 법도 한데... 일단 이렇게 해보자.

각 숫자에 대해 주어진 m개의 숫자를 포함하는지 확인하는 부분에서 살짝 까다로웠지만 일단 구현은 했다.
AC는 받았는데, 시간이 역시 엄청 걸렸다. 그리고 맞은 사람 목록을 보니 나보다 훨씬 시간이 적게 걸린 분들이 많고 심지어 0ms로 푸신 분들도 꽤 있다.

어떤 분의 코드를 봤는데 그 분의 코드는 n, m만 입력 받길래 도대체 다른 입력은 어디서 받는 건가 궁금해서 실행해봤더니 다른 입력은 받지 않고 그냥 n, m만 입력하면 답이 나온다...?! 헉.. 아... 그렇다.. 그런 것이다. 바로 m만 알면 m개의 수가 어떤 수이든 간에(문제에서 서로 다른 수라고 했으니) 경우의 수는 똑같이 나오는 것이다...!!!
와...생각도 못했었네...  그 분의 코드를 살펴보니 매우 짧고 간결한데 분석해본 결과 다음과 같다.
일단, 모든 수를 구하시긴 하는데 bit연산과 재귀를 이용해서 구한다. 예를 들어 3자리 수라고 하면 각 자리에서 어떤 수를 선택했는지를 표시하는 것이 아닌 0부터 9중 어떤 수를 선택했는지만 표시한다. 각 자리별로 dfs 깊이를 들어가면서 (즉 깊이는 자리 수 만큼 들어가게 된다) 0부터 9중에 어떤 수를 선택하는지 기록한다. 결국 모든 경우를 다 보게 되고, 마지막 자리까지 다 선택한 후 위의 m개의 수가 어떤 수든 간에 똑같다는 것을 이용해서 미리 만들어 놓은 (1<<m)-1 즉  0, 1, .., m-1까지의 수 자리를 1로 채워놓은 것과 &연산을 통해서 (1<<m)-1이 그대로 나온다면 0부터 m-1까지의 수 즉, m개의 수가 포함되었다는 것이므로 카운트를 한다....

와우.. 위의 방법은 모든 경우를 구하되 정말 딱 필요한 것만 쓴 그런 방법 같다. 멋지다. 재귀를 통해 모든 경우를 다 구하고 (그렇게 안 보이지만 다 구하는 거나 마찬가지) 비트 연산을 적절히 활용해서 m개의 수가 포함되었는지 계산하는 정말 멋있는 방법같다.

자 이제 0ms 코드를 분석해 봐야겠다.
근데 이해는 잘 못하겠다.
대충 식을 써보면
10^n - nC1 * 9^n + nC2 * 8^n - nC3 * 7^n + .... 이런 식으로 덧셈 뺄셈을 번갈아 가면서... 가는 왠지 어디선가 본 모양의 식이다. 익숙하긴 한데.. 모르겠다. 아 수학 공부 열심히 할 걸... 후회할 건 후회하고 지금부터 열심히 하면된다. 늦었지만 안 하는 것보단 훨씬 낫다.

이 문제는 수학 공부좀 해보고 다시 도전해보자. 정수론, 이산수학, 고등수학...