Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

33. 동적 계획법3

비트마스크를 배우고, 동적 계획법에 적용해 봅시다. 그 후에는 선형이 아니라 원형으로 구성된 문제를 다룹니다.

6. 색상환

2482번

원에서 인접하지 않게 색을 선택하는 문제

이번 문제는 주어진 정수 N과 K에 대하여, N개의 색으로 구성되어 있는 색상환 (N색상환)에서 어떤 인접한 두 색도 동시에 선택하지 않으면서 서로 다른 K개의 색을 선택하는 경우의 수를 구하는 문제이다.

dp로 풀 수 있는 문제이다. dp[i][j] = k => i개의 색이 있을 때, j개의 색을 선택할 수 있는 경우의 수 = k 임을 의미한다.
1~n개의 색이 있다면, n번째 색을 선택한 경우 + n번째 색을 선택하지 않은 경우를 아래와 같이 구할 수 있다.

n번째 색을 선택한 경우 → n - 1번째 색은 선택하지 못하므로 dp[n - 2][k - 1]이 되고, n번째 색을 선택하지 않는 경우 → n - 1개 중에서 k개를 선택하는 경우와 같으므로 dp[n - 1][k]가 된다.
따라서 dp[n][k] = dp[n - 2][k - 1] + dp[n - 1][k] 이다.
여기서 정답은 n번째 색을 선택한 경우 + n번째 색을 선택하지 않은 경우를 구하면 된다. (n번째 색을 선택한 경우 1도 제외 => dp[n - 3][k - 1])
(n개 중 n/2개 보다 색을 더 많이 고를 수는 없어, j의 범위를 코드와 같이 설정한다.)

Java / Python

• Java

import java.io.*;

public class Main {
	private static final int MOD = 1_000_000_003;
	static int N, K;
	static int[][] dp;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());
		K = Integer.parseInt(br.readLine());

		dp = new int[N + 1][N + 1];

		// dp 초기화
		for (int i = 1; i <= N; i++) {
			dp[i][1] = i;
			dp[i][0] = 1;
		}

		for (int i = 3; i <= N; i++) {
			for (int j = 2; j <= (i + 1) / 2; j++) {
				// i번째 색을 선택하지 않은 경우 + i번째 색을 선택한 경우
				dp[i][j] = (dp[i - 1][j] + dp[i - 2][j - 1]) % MOD;
			}
		}

		bw.write((dp[N - 3][K - 1] + dp[N - 1][K]) % MOD + "\n");

		bw.flush();
		bw.close();
		br.close();
	}
}

• Python

import sys
input = sys.stdin.readline
MOD = 1000000003
        
N = int(input())
K = int(input())

dp = [[0]*(N+1) for i in range(N+1)]

for i in range(N + 1):
    dp[i][0] = 1
    dp[i][1] = i

for i in range(3, N + 1):
    for j in range(2, int((i + 1) / 2)+1):
        dp[i][j] = (dp[i - 1][j] + dp[i - 2][j - 1]) % MOD

print((dp[N - 3][K - 1] + dp[N - 1][K]) % MOD)