백준 1670번. 정상 회담 2 (Java)

문제 링크 : https://www.acmicpc.net/problem/1670

원탁에 있는 사람들이 손을 교차하지 않고 모두 악수하는 경우의 수를 찾는 문제입니다.

문제를 읽으면 Dynamic Programming 이 떠오릅니다.

핵심은 두 사람이 악수를 하면 그 두 사람을 기준으로 두 개의 영역이 만들어집니다.

그럼 그 영역에 있는 사람들끼리 악수하는 경우를 구하면 됩니다.

위 사진을 보면 총 6명의 사람이 원탁에 앉아있는 상황입니다.

만약 가운데 있는 두 사람이 악수를 한다면 저렇게 빨간 선처럼 악수를 하겠죠.

저 선을 기준으로 서로 맞은 편에 있는 사람들은 악수를 하지 못합니다.

결국 선을 기준으로 파란색 동그라미친 두개의 영역이 생성된거죠.

위 사진은 한가지 예시일 뿐이고, 사람이 많아질수록 경우의 수는 더 커집니다.

위 사진처럼 8명의 사람이 있다고 가정합니다.

그럼 총 4가지의 큰 경우의 수가 생깁니다.

1. 0과 1이 악수하는 경우

2. 0과 3이 악수하는 경우

3. 0과 5가 악수하는 경우

4. 0과 7이 악수하는 경우

1. 0과 1이 악수한다면 사실상 영역이 나누어지지 않습니다.

dp[0]인 거죠. 나머지 인원은 6명이기 때문에 6명이 악수하는 경우의 수 dp[6] 입니다.

2. 0과 3이 악수한다면 위에는 2명, 아래는 4명이 생깁니다.

dp[2] * dp[4] 가 2번의 모든 경우의 수입니다.

3. 0과 5가 악수한다면 위에 4명 아래 2명 = dp[4] * dp[2]

4. 0과 7이 악수한다면 dp[6] * dp[0]

이렇게 4가지의 모든 경우의 수를 구한다음에 더해주면 총 경우의 수가 나옵니다.

0이 2, 4, 6과 악수하지 않는 이유는 사람이 홀수면 악수하는 인원이 딱 나누어 떨어지지 않기 때문입니다.