BOJ 2482 - 색상환

문제

N개의 색이 원형으로 배치된 색상환에서 인접하지 않은 K개의 색을 선택하는 경우의 수를 구하라.

입력

첫째 줄에 N, 둘째 줄에 K가 주어진다.

출력

경우의 수를 1,000,000,003으로 나눈 나머지를 출력한다.

예제

입력	출력
`4` `2`	`2`

풀이

원형 배열에서 인접하지 않는 선택의 점화식으로 메모이제이션 재귀를 수행한다.

dp[N][K]를 N개 중 인접하지 않게 K개 선택하는 경우의 수로 정의한다
점화식: dp[N][K] = dp[N-2][K-1] + dp[N-1][K] (마지막 색 선택/미선택)
기저 조건: K=1이면 N, K = ceil(N/2)이면 2 (최대 선택)
N/K < 2이면 선택 불가하므로 0을 출력한다

핵심 아이디어: 원형 배열의 비인접 선택은 선형의 경우와 같은 점화식을 따르되, 기저 조건에서 원형 성질(처음과 끝이 인접)을 반영한다.

코드

package day449;
 
import java.io.*;
 
public class Day401BOJ2482색상환 {
  static final int MOD = 1000000003;
  static int N, K;
  static int[][] dp;
 
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    N = Integer.parseInt(br.readLine());
    K = Integer.parseInt(br.readLine());
 
    dp = new int[N + 1][K + 1];
 
    if (N / K < 2) {
      System.out.println(0);
      return;
    }
 
    System.out.println(recur(N, K));
    br.close();
  }
 
  public static int recur(int N, int K) {
    if (K == 1) {
      return N;
    }
 
    if (K == (N / 2 + N % 2)) {
      return 2;
    }
 
    if (dp[N][K] == 0)
      dp[N][K] = (recur(N - 2, K - 1) + recur(N - 1, K)) % MOD;
 
    return dp[N][K];
  }
}

복잡도

시간: O(N * K) - 메모이제이션 상태 수
공간: O(N * K)

문제