HandShaking

문제

둥근 테이블에 앉아 회의하는 n명의 직장인이 있다

회의 시작시 반드시 다른 사람과 악수를 해야 한다

악수는 동시에 수행하며, 악수하는 팔끼리 교차되지 않아야 한다

n명의 직장인이 하는 악수가 성립하는 조합의 수를 리턴한다

• n 은 2 ~ 50의 짝수이다

예시 입력

2
4
8

예시 출력

1
2
14

생각의 변화

가로지르는 경우에 대해 표현해보면

번호를 붙인다

짝수별로 돌면서 선택, 이때 홀수만 선택가능

이전단계가 선택한 홀수, 이번단계 홀수
O(n-1)               O(n)

0                    2 가
선택할수 있는 홀수는

1 나(2)보다 작은수     3 5 7 다 가능
3 나(2)보다 큰 수      1 넘지않게
5                     1 3 
7                     1 3 5

코드로 옮기면

if Odd(n-1) < Even(n)
    Odd(n) = all
else
    Odd(n) = Odd(n-1) 보다 작은 것들

각 선택에 따른 odd 변경은 아래로 전파되어야 한다
ret = 1

내 위치도 전파

odd 는 점점 감소, odd 가 0이 될때까지

이전 선택에 따라 odd 가 결정되니
그럼 최초 선택은

선택한건 odd 에서 제거

순회중에 변경하면 x

e+2 가 n 넘는 경우는 0 리턴
odd 가 빈 경우 1 리턴

빌때가지 순회하면서 리턴값 누적
최종적으로 획득

pseudo code

countPerfect(n)
    vector<int> odd
    
    for i=1  i<n  i=i+2
        odd.push_back(i)
        
    ret = 0
    vector<int> next_odd = odd
    
    for auto o : odd
        next_odd.erase(next_odd.begin())
        
        ret += dfs(0, o, next_odd, n)
        
        next_odd.push_back(o)
        
    return ret

dfs(e, o, odd, n)
    if e >= n
        return 0
        
    if odd.size() == 0
        return 1
        
        
    vector<int> next_odd
    ret = 0

    if (o < e+2)
        next_odd = odd
        
        for (auto _o : odd)
            next_odd.erase(next_odd.begin())
            
            ret += dfs(e+2, _o, next_odd, n)
            
            next_odd.push_back(_o)
            
    else
        vector<int> tmp
        
        for (auto _o : odd)
            if _o < o
                tmp.push_back(_o)
                
        next_odd = tmp
        
        for (auto _o : tmp)
            next_odd.erase(next_odd.begin())
            
            ret += dfs(e+2, _o, next_odd, n)
            
            next_odd.push_back(_o)
            
    return ret