[BaekJoon] 2482 색상환 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/2482

2.  문제

요약

• 색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 합니다.
• 색상환에서 인접한 두 색은 비슷하여 언뜻 보면 구별하기 어려워 시각적 대비 효과를 얻기 위해 인접한 두 색을 동시에 사용하지 않기로 하였습니다.
• 주어진 정수 N과 K에 대해, N개의 색으로 구성되어 있는 색상환(N색상환)에서 어떤 인접한 두 색도 동시에 사용하지 않으면서 서로 다른 K개의 색을 선택하는 경우의 수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 4보다 크거나 같고 1,000보다 작거나 같은 양의 정수인 색상환에 포함된 색의 개수를 나타내는 N이 주어지고 두 번째 줄에 1보다 크거나 같고 N보다 작거나 같은 M색상환에서 선택할 색의 개수 K가 주어집니다.
• 출력: 첫 번째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003으로 나눈 나머지를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static final int MOD = 1_000_000_003;
    static int N, K;

    static void input() {
        Reader scanner =  new Reader();

        N = scanner.nextInt();
        K = scanner.nextInt();
    }

    static void solution() {
        if(K > N / 2) {
            System.out.println(0);
            return;
        }

        int[][] dp = new int[N + 1][N + 1];
        init(dp);

        for(int colorNum = 4; colorNum <= N; colorNum++) {
            for(int chosenNum = 2; chosenNum <= (K < (colorNum / 2) ? K : (colorNum / 2)); chosenNum++) {
                dp[colorNum][chosenNum] = (dp[colorNum - 2][chosenNum - 1] + dp[colorNum - 1][chosenNum]) % MOD;
            }
        }

        System.out.println(dp[N][K]);
    }

    static void init(int[][] dp) {
        for(int colorNum = 1; colorNum <= N; colorNum++)
            dp[colorNum][1] = colorNum;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 인접한 색은 고를 수 없기 때문에 최대로 고를 수 있는 색의 개수는 N / 2입니다.
• 그러므로 K가 N / 2보다 크다면 0이 답이 됩니다.

• K가 N / 2보다 작거나 같다면 DP를 통해 문제를 해결합니다.
• DP를 위해 2차원 배열 dp를 생성하는데, 이는 다음을 의미합니다
  • dp[x][y] = x개의 색에서 y개의 색을 고르는 경우의 수
• 색을 고르는 경우의 수를 생각해봤을 때, 마지막 색을 고르는가 안고르는가로 나눠서 생각해볼 수 있습니다.
  • 예를 들어, 색이 8개가 있다고 생각했을 때 아래와 같이 나눠볼 수 있습니다.
    • 8번째 색을 선택했을 때
    • 8번째 색을 선택하지 않았을 때
  • 8번째 색을 선택했다면, 1번째 색은 인접하여 선택할 수 없기 때문에, 나머지 6개의 색으로 y - 1개의 색을 골라야 합니다.
  • 이를 식으로 써보면 아래와 같습니다.
    • dp[x - 2][y - 1]
  • 8번째 색을 선택하지 않았다면, 나머지 7개의 색에서 y개의 색을 골라야 합니다.
    • 이를 식으로 써보면 아래와 같습니다.
    • dp[x - 1][y]
  • 위 두 가지 경우가 존재하므로 최종적으로 아래와 같이 나타낼 수 있습니다.
    • dp[x][y] = dp[x - 2][y - 1] + dp[x - 1][y]

• 색을 하나를 고를 때에는 존재하는 색의 개수가 경우의 수가 되기 때문에 dp[N][1]은 N이 됩니다.
  • 그러므로 dp의 첫 번째 열은 모두 1로 값을 초기화시킵니다.
• 또한, 2개 이상의 색을 고르려면 최소 4개의 색이 존재해야 합니다.
  • 그러므로 색의 개수가 4개일 때부터 N개가 될 때까지 반복문을 돌면서 골라야하는 색의 개수마다 경우의 수를 위 점화식을 통해 구합니다.
    • 골라야하는 색의 개수를 2개일 때부터 (K, 색의 개수 / 2)에서 작은 값까지 돌면서 색의 개수를 x, 골라야하는 색의 개수를 y라고 한다면 ((dp[x - 2][y - 1] + dp[x - 1][y]) % 1,000,000,001)을 구해 dp[x][y]에 넣습니다.
• 위 작업을 모두 마치고 난 후의 dp[N][K]가 답이 됩니다.