[알고리즘][6][백준_1670][Python3] - 정상 회담 2

---

문제 이해

문제자체는 간단하지만 n이 조금만 커져도 경우의수가 커지고 점화식도 쉽게 발견되지 않아 조금은 까다로웠던 문제였다.

서로 팔이 교차하지 않는 것을 중점으로 생각해봐야 할것같다.

 

 

---

알고리즘 전략

점화식에 접근할때 n이 주어졌을때 그 상황들을 분해하려고 고민을 했다.

 

먼저 n = 8 일때로 먼저 분석을 해보자. ( 편의상 n=k일때 가능한 경우의 수를 dp[k]라고 하자 )

 

n = 8 일때

이 상황에서 악수를 할수 있는 경우의 수를 찾다보면 한가지 규칙을 찾을 수 있다.

 

어떤사람과 어떤사람이 악수할때 그 둘 사이에 있는 사람의 수가 홀수가 되면 안된다는 것이다.

 

첫 사람이 잘못 악수한 경우들 - 나머지사람에서 교차가 무조건 생기게 된다.

따라서 파란색 점을 기준으로 할때 이 사람이 악수 할수 있는 사람은 위의 3점과 자신을 제외한 4개의 점이다.

 

파란색이 악수 할수있는 점은 다음과 같다. 

 

이제 위의 4가지 경우들 안에서 가능한 모든 경우의 수들을 구한것이 dp[8]이 될것이다.

 

그런데 맨왼쪽과 맨오른쪽, 그리고 가운데 두가지는 좌우 반전만 되었을뿐 그 내부 구조는 같다.

 

따라서 4가지상황을 모두 고려할 필요없이 좌측 2개의 상황만 고려해서 경우의 수를 구한뒤 2배를 해주면 된다.

 

 

#1

이경우 나머지 6명이 악수하는 경우의 수가 되므로 dp[6] 이될것이다.

 

다음과정에서 이해하기 쉽게 dp[0]*dp[6]이라고 하자 (dp[0]은 0명이 악수하는 경우의 수 이므로 1)

 

 

 

#2

이경우 악수한 선 기준으로 좌측과 우측으로 보면

 

좌측은 2명이 악수하는경우 dp[2]

우측은 4명이 악수하는경우 dp[4]

 

이 둘이 독립이므로 dp[2]*dp[4]가 될것이다.

 

따라서 정리하면

 

dp[8] = ( dp[0]*dp[6] + dp[2]*dp[4] ) * 2 

 

가 될것이다.

 

 

위 예시를 보면 8일때를 구하는데 2,4,6일때의 경우가 모두 쓰였다.

 

몇가지 경우를 더 살펴보면 

 

dp[n]을 구할때 dp[n-2-k]*dp[k] + ... 의 꼴이 나오는것을 알수 있고 

 

또한 n이 4의 배수일때는 위와같이 전체 구한경우의수에 2를 곱해서 최종 답을 도출해냈지만

 

그렇지않은 수 (10, 14, 18 등등.. ) 에서는 마지막 dp[(n-2)/2]*dp[(n-2)/2] 빼고 2배를 해야함을 알수있다.

 

n = int(input(""))

dp = [0] * 10001
dp[0] = 1
dp[2] = 1
dp[4] = 2
i = 6
while(i <= n):
    total = 0
    for j in range(i//4): # n이 4의 배수던 아니던 공통이다
        j = j*2
        total = total + dp[j]*dp[i-j-2]*2

    if(i%4 == 2): # n이 4의 배수가 아닐때만 아래경우를 더해주어야한다
        total = total + dp[(i-2)//2]*dp[(i-2)//2]
    dp[i] = total%987654321
    i = i+2

print(dp[n])

 

보통 점화식에서 n을 구할때 n-1이나 n-2까지만 고려하면 구할수 있었는데

 

이문제같은경우 n을 구할때 그 이전에 구했던 n-k들을 모두 이용했다는 점에서 조금 까다로웠다.