dp 05 악수

 

구현해야 하는 함수 public long countPerfect(int n)

제약 조건 n : 2~50의 짝수

 

오케이.. 10분정도 고민해보자..

만약 전체탐색을 하게 된다면.. 음.. n! 비례하는 시간복잡도가 나올라나?

후보가 1번부터 n번까지 있고 악수할 사람이 다 정해졌을 때 엇갈린지 안엇갈린지는 어떻게 판단하지?

어? 잠깐만..!!!

직관을 얻은듯..!

자 예를 들어 후보가

1번 2번 3번 4번 5번 6번 7번 8번 9번 10번이 있고

1번이 6번이랑 악수하기로 했다고 치자

그럼 악수가 안 엇갈리려면

이렇게 1번 6번을 연결하고 양쪽으로 끼리끼리 악수하는 상황이 되어야 하잖아.

그니까 1-6이 악수를 하면 2~5와 7~10이 각각 끼리끼리 악수를 해야된다는거지.

2~5에 속한 사람이랑 7~10에 속한 사람이 악수를 할 수는 없는거지.

일반화하면 x랑 y가 (x<y) 악수하기로 했을 때

x+1~y-1 끼리 악수를 하고

y+1~x-1 끼리 악수를 해야된다는것..!

 

잠깐 근데 이게 왜 dp문제지?

내 생각엔.. x번 사람~y번 사람 끼리 악수하는 경우의 수를 메모해놔야될듯 하다?

왜냐면 꼭 1-6 악수하는 경우 뿐만 아니라 10-1이 악수하고 9-6, 8-7이 악수하는 경우도 2~5의 악수하는 경우를 세야 되니까. x~y끼리 악수하는 경우의 수를 또 쓸일이 있단말이지?

x~y끼리 악수하는 경우의 수는 y-x+1 즉 몇 명이냐에 따라 결정되는거같다. 2~5면 4명이니까 무조건 경우의수는 2. 이런식으로. 

2명이면 둘이 악수하니까 1.

4명이면 엇갈리는 경우 제외하면 2.

6명이면 후보가 1 2 3 4 5 6

1번사람이 2랑 악수할수도 있고 4랑 악수할수도있고(3은 안됨. 2가 할사람이 없어짐) 6이랑 악수할 수도 있다.

1-2가 악수하면 나머지 3~6은 4명이니까 경우의 수는 2.

1-4가 악수하면 2~3, 5~6 각각 2명씩 짝지어 악수를 해야되니까 경우의 수는 1 * 1 = 1.

1-6이 악수하면 2~5는 4명이니까 경우의 수는 2.

다 합치면 경우의 수가 5.

그니까 일차원 배열 handshake[]를 만들어서 handshake[i]에 i명이 악수할 경우의 수를 적어주면 되겠다.

f(6) = f(4) + f(2) * f(2) + f(4)

f(8) = f(6) + f(4) * f(2) + f(2) * f(4) + f(6)

규칙이 보인다. f(2)가 1이니까 위 식을 살짝 변형하면

f(6) = f(4) + f(2) * f(2) + f(4)

f(8) = f(6) + f(4) * f(2) + f(2) * f(4) + f(6)

 

f(2)를 dp[1]에 넣고

f(4)를 dp[2]에 넣고

f(6)을 dp[3]에 넣자

 

dp[3] = dp[2] + dp[1] * dp[1] + dp[2]

dp[4] = dp[3] + dp[2] * dp[1] + dp[1] * dp[2] + dp[3]

 

dp[i] = dp[i-1] + dp[i-2] * dp[1] + ... dp[1] * dp[i-2] + dp[i-1]

맨 앞이랑 맨 뒤의 dp[i-1] 만 곱셈이 없으니까 dp[0] = 1이라 치고 붙여주자

dp[i] = dp[i-1] * dp[0] + dp[i-2] * dp[1] + ... dp[1] * dp[i-2] + dp[0] * dp[i-1]

 

base case dp[0]=1, dp[1]=1 가지고 반복문을 돌려보자잇

 

 

def count(n):
    dp = [0] * (n//2 + 1)

    dp[0] = dp[1] = 1

    for i in range(2,n//2 + 1):
        for j in range(i):
            dp[i] += dp[j] * dp[i-j-1]

    return dp[i]

print(count(50))

 

이 문제는 수학적으로도 풀 수 있는데 '카탈랑 수'라고 불린다고 한다.

실제로 출력해보니까 인터넷에 나와있는 카탈랑 수 수열이랑 똑같다 ㄷㄷ

 

이로써 topcoder알고리즘 책에 나와있는 dp 문제를 다 풀었다.

이제 전체탐색 문제들을 풀어야지.

생각해보니까 이 책 전체적인 챕터 흐름이 전체탐색->dp->탐색범위한정->그래프 로 간다.

되게 체계적으로 구성돼있었네 ㄷㄷ.. 지금이라도 전체탐색 풀기 시작해야겠다.