BOJ 1670 정상 회담 2

원탁에 N명(짝수)의 사람이 앉아있고, 서로 동시에 악수를 하되 팔이 겹치지 않게 악수하는(문제에 따르면 완벽한 악수를 하는) 경우의 수를 구하는 문제이다. dynamic programming으로 푸는 문제이다.
접근하기가 힘들어서 조금 생각하다가 백준님의 풀이를 봤다.

풀이를 보니... 내 자신이 한심해진다... 왜 생각을 못했지 딱히 새로운 생각이라고 할 것도 없는데...
일단 임의의 사람을 기준으로 하면, 편하게 1번사람을 기준으로 하면 짝수명이기 때문에 한 사람도 빠짐없이 악수를 하게 될 것이고 모든 경우에서 1번 사람은 누군가와 악수를 할 것이다. 그러므로 모든 경우는 1번 사람이 누구랑 악수를 하느냐로 나눌 수 있다.
1번 사람이 2번과 악수를 하는 경우, 3번과 악수를 하는 경우, 4번과, 5번과... n번과 악수를 하는 경우로 나눠진다. d[i]=i명이 완벽한 악수를 하는 경우의 수 라고 하면 1번 사람이 j번 사람과 악수를 하는 경우의 수는 d[i-j]*d[j-2] 가된다. 그리고 우리가 구하고자 하는 값은 d[i]=SUM(j=2 ~ j=n) (d[i-j]*d[j-2]) 가 된다.(시그마를 쓰고 싶었는데, 어떻게 쓰는지 몰라서 일단 이렇게 표현) 백준님 강의 자료에 보면 이 문제를 푸는 방법이 올바른 괄호 문자열의 개수를 세는 문제와 같다고 돼있는데, 일단 위의 방법대로 풀어보고 생각해 봐야겠다.

문제를 풀면서 생각해야할 것... d[i]에서 i값이 0인 경우는 1을 return해주면 되고, 홀수인 경우는 악수가 교차되어 완벽한 악수가 아니므로 0을 return해주면 된다. 처음에 틀렸는데, MOD로 나눠주기 때문에 넘어갔던 것인데 바로 곱셈시 int형 범위를 넘을 수 있는 것이 문제였다. 그래서 long long형으로 바꿔서 AC를 받았다. 근데 실행시간이 매우 느린 편이다...

백준님의 코드를 보니 점화식이 좀 다른 것도 있지만(한 번 올바른 괄호 문자열의 개수 문제를 풀어봐야겠다.) 내 코드에서 시간이 많이 드는 것이 modulo를 한번 더 해준 것 때문인 것 같다. 예전에 알고리즘 캠프에서 modulo 나 나누기 연산이 시간이 많이 걸린다고 들은 것 같은데, 내가 modulo를 한 부분은

곱셈을 하고 modulo를 해줘야 해서 한 것인데, 저 부분은 안해도 된다 즉

이렇게 해줘도 똑같다.
dp(n-i)*dp(i-2)의 값을 a*MOD + k, ret값을 0*MOD+t라고 하면,
위에서 처럼 미리 MOD를 한 번 해주면 ret는 (k+t)%MOD가 되는데, 미리 MOD를 하지않고
마지막에 가서 MOD를 한 번만 하더라도
ret+=dp(n-i)*dp(i-2)연산 이후 ret는 a*MOD+k+t이다.
결국 ret%=MOD를 하면 (k+t)%MOD가 된다.  그러므로 같다. 고쳐서 제출 했더니 일단 시간이 반정도 줄었다. 하지만 여전히 느리긴하다.

2016년 9월 26일, 다시 풀어보는데 int형으로 하기 위해서 modulo를 위에서 처럼 미리 한 번, 더하고 한 번 총 두 번 해줬는데, int형이라 그런지 시간은 long long으로 modulo 한 번 했을 때와 똑같이 나왔다.
물론 중간에 곱셈에서 int형 범위를 넘어가므로 (long long)형 변환을 붙여줘야 한다. 그리고 MOD로 나눈 나머지를 더해야하고..

출처 : 백준님 강의, 강의 자료.