BOJ_2482_색상환 (Java)

[Gold III] 색상환 - 2482

문제 링크

성능 요약

메모리: 16568 KB, 시간: 120 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 2월 12일 16:18:35

문제 설명

색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다. 미국의 화가 먼셀(Munsell)이 교육용으로 고안한 20색상환이 널리 알려져 있다. 아래 그림은 먼셀의 20색상환을 보여준다.

그림 1. 먼셀의 20색상환

색상환에서 인접한 두 색은 비슷하여 언뜻 보면 구별하기 어렵다. 위 그림의 20색상환에서 다홍은 빨강과 인접하고 또 주황과도 인접하다. 풀색은 연두, 녹색과 인접하다. 시각적 대비 효과를 얻기 위하여 인접한 두 색을 동시에 사용하지 않기로 한다.

주어진 색상환에서 시각적 대비 효과를 얻기 위하여 서로 이웃하지 않은 색들을 선택하는 경우의 수를 생각해 보자. 먼셀의 20색상환에서 시각적 대비 효과를 얻을 수 있게 10개의 색을 선택하는 경우의 수는 2이지만, 시각적 대비 효과를 얻을 수 있게 11개 이상의 색을 선택할 수 없으므로 이 경우의 수는 0이다.

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

입력

입력 파일의 첫째 줄에 색상환에 포함된 색의 개수를 나타내는 양의 정수 N(4 ≤ N ≤ 1,000)이 주어지고, 둘째 줄에 N색상환에서 선택할 색의 개수 K(1 ≤ K ≤ N)가 주어진다.

출력

첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다.

문제 풀이

원형 구조를 선형으로 바꿔 DP로 계산한 후, 원형 특성으로 인한 중복을 제거하는 방식

코드

2차원DP 풀이

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, K;
    static int[][] dp;
    static final int MOD = (int)1e9 + 3;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_2482_색상환/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        if(K > N/2) {
            System.out.println(0);
            return;
        }
        if(K==1) {
            System.out.println(N);
            return;
        }

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

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


        for(int i=2; i<=N; i++){
            for(int j=2; j<=N/2; j++){
                dp[i][j] = (dp[i-2][j-1] + dp[i-1][j]) % MOD;
            }
        }

        int selectFrom1 = dp[N-3][K-1] % MOD;
        int selectFrom2 = dp[N-1][K] % MOD;
        bw.write(String.valueOf((selectFrom1 + selectFrom2) % MOD));
        bw.flush();
        bw.close();
        br.close();
    }
}

---

1차원 DP 풀이

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, K;
    static int[] dp;
    static final int MOD = (int)1e9 + 3;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_2482_색상환/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        if(K > N/2) {
            System.out.println(0);
            return;
        }
        if(K==1) {
            System.out.println(N);
            return;
        }

        dp = new int[K + 1];

        for(int i=0; i<=K; i++){
            dp[i] = 1;
        }

        for(int len = 1; len <= N-2*K+1; len++) {
            for(int j=1; j<=K; j++) {
                dp[j] = (dp[j] + dp[j-1]) % MOD;
            }
        }

//        System.out.println(Arrays.toString(dp));

        System.out.println((dp[K] - dp[K-2] + MOD)%MOD);
        bw.flush();
        bw.close();
        br.close();
    }
}

1. 바깥쪽 반복문 (len):

• 목적: 각 색을 하나씩 추가해가며 경우의 수를 누적합니다.

• N - 2*K + 1 계산 이유:

  • K개의 색을 선택하려면 최소 (K-1)개의 “건너뛸 색”이 필요합니다.

  • 예: K=2면 1칸 띄워야 하므로 최소 2K-1 = 3개의 색이 필요 → N >= 3K-1

  • 이 조건을 만족하는 범위 내에서 색을 추가합니다.

2. 안쪽 반복문 (j):

• 점화식 dp[j] = dp[j] + dp[j-1]의 의미:

  • dp[j] (선택 안 함): 이전까지 j개 선택한 경우 그대로 유지

  • dp[j-1] (선택 함): 새로운 색을 선택하면 j-1개에서 j로 증가

  • → 두 경우를 합친 것!

1. 최종 결과 계산 (dp[K] - dp[K-2]):

• dp[K]: 선형으로 계산한 모든 경우 (원형 고려 X)

• dp[K-2]: 첫 번째와 마지막 색을 동시에 선택한 경우 (이를 제외해야 함)

  • 예: N=4, K=2일 때, dp[K] = 3 (1-3, 1-4, 2-4)

  • dp[K-2] = dp[0] = 1 (첫 번째와 마지막을 선택하면 중간 2개는 선택 불가)

  • 3 - 1 = 2 (정답)