[문제해결을 위한 창의적 알고리즘] 색상환 (고급, p131)

이 문제는 점화식을 유추해 내기 그렇게 쉽지는 않은 문제였다. 그래서 해설에서도 점화식을 유도하는 데 상당한 분량을 할애하고 있다. 점화식이 이해가 된다면 코드를 이해하는 것은 큰 문제 없을 것 같다. 재귀함수를 통한 구현 방법을 먼저 아래에 적어 보겠다.

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, k))%MOD;

}

public static void main(String[] args) {

int n, k;

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

k = sc.nextInt();

sc.close();

System.out.println(f(n,k));

return;

}

}

Big O(2^n)

github 주소: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/ColorCircleSol136.java

문제해결을 위한 창의적 알고리즘 목록