색상환
-
[문제해결을 위한 창의적 알고리즘] 색상환 2 (고급, p131)알고리즘 2017. 2. 1. 09:56
이전 포스트에서는 가장 기초적(?)인 방법을 소개했는데 이번에는 책에서 설명하는 방법 중 가장 효율적인 방법을 적어보고자 한다. 사실 점화식을 유도해 내는 과정이 좀 어렵게 느껴져서 그렇지 이전의 방법으로 문제를 풀 수 있었다면, 동적 계획법 (dynamic programming)으로 바꿔서 푸는 것은 그렇게 어려워 보이지 않는다. n개 색상중 k개를 뽑는 방법은 k가 1이면 n이라는 것과 k가 n/2를 넘으면 0이라는 것, 그외의 경우에는 n-2에서 k-1개를 선택하는 것과 n-1개에서 k개를 선택하는 것을 더하면 된다는 것을 유도해 내는 것이 중요하다. import java.util.Scanner; public class ColorCircleSol138 { public static final int ..
-
[문제해결을 위한 창의적 알고리즘] 색상환 (고급, p131)알고리즘 2016. 8. 15. 19:45
이 문제는 점화식을 유추해 내기 그렇게 쉽지는 않은 문제였다. 그래서 해설에서도 점화식을 유도하는 데 상당한 분량을 할애하고 있다. 점화식이 이해가 된다면 코드를 이해하는 것은 큰 문제 없을 것 같다. 재귀함수를 통한 구현 방법을 먼저 아래에 적어 보겠다. C에서 #define은 자바에서 final 키워드를 이용해 처리하였다. import java.util.Scanner; public class ColorCircleSol136 { public static final int MOD = 1000000003; public static int f(int n, int k) { if (k>n/2) return 0; else if (k==1) return n; else return (f(n-2, k-1)+f(n-1,..