2019-2) handshaking

Q. 월요일에 원탁에 회의를 하려고 직원들이 모여 있다. 회의 시작 전에 서로 악수를 하려고 하는데 팔이 겹치지 않게 하면서 모두 악수를 하는 방법의 수를 구하시오. (인원은 짝수)

 

입력 = 2 -> 출력 = 1

입력 = 6 -> 출력 = 5

 

Tip1. 

 

ex) 10명

2-3이 악수하는 경우와 3-7이 악수하는 경우가 독립적 -> 더하기

3-7이 악수하는 경우 나눠진 양쪽끼리 악수 -> 곱하기

.

.

a-b가 악수하는 경우 나눠지는 양 쪽끼리 악수하는 경우를 모두 더함

 

 

Tip2.

N = 2) H2 = 1

N = 4) H4 = (H2 + H0) + (H0 + H2) = 2

N = 6) H6 = (H4 + H0) + (H2 * H2) + (H0 + H4) = 5

* 다른 의견이 있으시면 피드백 받겠습니다.