dynamic programming 5

2015. 1. 6. 09:33Security ★ Development/알고리즘

반응형

문제는 더블릿 21 dynamic programming에 있는 gc입니다.

문제 사이트 주소입니다.

http://183.106.113.109/30stair/gc/gc.php?pname=gc


입력으로 주어진 수 n을 1부터 n*2까지 차례대로 원 위에 쓰고 서로 엇갈리지 않게 선을 그을 수 있는 전체 경우의 수를 구하는 문제입니다.


이 문제에는 규칙이 있습니다.  n=3일 때를 보면 1-2를 그었을 때 남은 숫자는 4개로 이를 서로 엇갈리지 않게 그을 수 있는 방법은 n이 2일 때와 같습니다.  n=4일 때는 1-2를 그었을 때 남은 숫자가 6개로 이는 n=3일 때의 모든 경우의 수와 같습니다.

즉 다음 경우의 수를 구하는데 이전 n값의 답을 구할 필요가 있습니다.  

이 규칙을 보면 1->? 로 가는 선을 구하는데 ?는 n+1까지만 구하면 된다는 것을 알 수 있습니다.

n=3일 때, 1->4로 선을 그었을 때 좌우는 대칭적인 경우를 보여줍니다.  

n=4일 때,

1->2 일 때 좌우 모두 6개씩 남았을 때의 경우의 수이고 

1->4 일 때 좌우는 각각 4개, 2개가 남았을 때 경우의 수입니다.

4개가 남았다는건 n=2일 때의 값이고 2개가 남았다는건 n=1일 때의 값입니다.

6개가 남으면 n=3일 때의 값이죠.

그리고 1->?에서 ?는 짝수만 올 수 있습니다.

이 ?를 1과 정반대에 있는 값인 n+1까지 해주며 n+1은 짝수가 아닐 수도 있습니다.


위와 같은 규칙을 n=2일 때부터 입력값까지 구하고 입력값일 때의 값을 출력하면 됩니다.



'Security ★ Development > 알고리즘' 카테고리의 다른 글

dynamic programming 6  (0) 2015.01.07
함수 2  (0) 2015.01.07
배열 1  (0) 2015.01.04
graph, dfs 2  (0) 2015.01.04
graph, dfs 1  (0) 2014.12.30