2015. 1. 6. 09:33ㆍSecurity ★ 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 |