2011. 4. 1. 13:55 프로그래밍/알고리즘
2009 KOI 중등부 2번.
오른쪽 끝에서 부터 1 , 2, ... 이라고 번호를 매겼을 때 ,
C[i,j] 는 위는 1~i , 아래는 1~j 까지 고려했을 때 가능한 경우의 수.
c[i,j] 는 만약 i,j 스위치가 연결 되어있다면
c[i,j] = c[i-1,j-1] * 2;
연결 안되어있다면,
c[i,j] = c[i-1,j] + c[i,j-1] - c[i-1,j-1]; ( 빼 주는 부분은 중복 되어 계산 되기 때문에 한 번 배주는 것. 포함배제의 원리 )
를 완성하면 이제 c[n,n] 부터 backtrace 를 하면서 답을 유추해야 한다.
연결이 되지 않은 경우는 bit 가 1이 될 수 없으므로 j를 하나 감소
만약 연결이 되어있다면, c[i-1,j-1] 을 살펴봐서 갯수를 카운팅 해서 , 결정해나간다.
( 경우의 수를 구한 뒤 그것을 통해 index 를 찾아다는 보편적인 DP 의 방법을 사용하면 된다 )
'프로그래밍 > 알고리즘' 카테고리의 다른 글
| Dijkstra 다익스트라 ( V + E ) log E (0) | 2011.12.13 |
|---|---|
| An old Stone Game. (0) | 2011.09.19 |
| Rebuilding Roads. (2) | 2011.03.17 |
