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

이전 포스트에서는 가장 기초적(?)인 방법을 소개했는데 이번에는 책에서 설명하는 방법 중 가장 효율적인 방법을 적어보고자 한다. 사실 점화식을 유도해 내는 과정이 좀 어렵게 느껴져서 그렇지 이전의 방법으로 문제를 풀 수 있었다면, 동적 계획법 (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 MOD = 1000000003;

public static int[][] DT = new int[1001][1001];

public static void main(String[] args){

int n,k;

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

k = sc.nextInt();

sc.close();

for (int i =2; i <=n; i++)

for (int j=1; j<=n/2; j++)

if (j==1)

DT[i][j]=i;

else

DT[i][j]=(DT[i-2][j-1]+DT[i-1][j])%MOD;

System.out.println(DT[n][k]);

return;

}

}

Big O(n^2)

Github: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/ColorCircleSol138.java

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

출처: 한국정보올림피아드 2010 지역본선 중고등부