BOJ G3 2482 색상환 JAVA

2482번: 색상환

---

문제 읽기

아 역시 DP 문제는 쉽지 않다. 사실 그렇게 어려운 문제인 것 같지는 않지만.. 처음에 DFS로 했다가 2^1000이니까 당연히 시간초과가 나고, 거의 바로 아 DP인 것 같다는 생각을 했다.

 

그런데 처음에 N, K로 접근하지 않고, 첫 번째 원소를 선택하는 경우, 첫 번째 원소를 선택하지 않는 두 가지 경우를 생각했다. 즉, N, 2로 접근했다. 그런데 이렇게 하니 DP 배열에 경우의 수를 저장하는 게 아닌, 선택한 원소의 개수를 저장하게 되고 답을 제대로 구하지 못했다.

 

그래서 질문 게시판을 참고하여 N, K 2차원으로 접근했다.

---

문제 풀기

일단 예제 문제를 표로 그려봤다.

넘 어렵당.. DP적인 사고를 잘 할 수 있으면 좋겠는데! 연습밖에 답이 없을 거 같다.

어쨌든 위에서 알 수 있는 정보는 다음과 같다.

• 2차원 DP 배열
• 점화식
• DP 배열 초기값
• 마지막 색상은 첫 번째 색상과 연결되어 있음

여기에 대해서 하나씩 알아보자.

DP 배열의 선언

dp 안에 들어가는 값은 경우의 수이다.

dp[i][j] : 색상 i개 중 j개를 선택하는 경우의 수

 

따라서 문제에서 주어진 조건에 따라 10억 3으로 나눈 나머지를 넣어주기 때문에, int 범위를 넘지 않는다. 따라서 다음과 같이 int 이차원 배열로 선언해주면 된다.

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

점화식 세우기

일단 논리적으로 접근하면 다음과 같다.

 

DP에서 n : 색상의 개수, k : 선택해야 하는 색상의 개수이다.

따라서 DP[n][k]의 값을 구하기 위해서 다음과 같은 논리를 거칠 수 있다.

• n번째 색상 선택하는 경우
  • n-1번째 색상을 선택하면 안 됨
  • 즉, n-2번째 색상에서 k-1개의 색상을 선택한 개수에 +1을 하면 됨
• n번째 색상을 선택하지 않는 경우
  • n-1번째 색상을 선택해도 됨
  • 즉, n-1번째 색상에서 k개의 색상을 선택한 개수를 담으면 됨

보통 DP는 두 경우 중 max를 담기 때문에 무지성으로 짜다 보면 max를 담을 수도 있는데.. 이 문제의 경우에는 N개의 색상에서 조건에 따라 K개를 선택하는 모든 경우의 수를 구하는 문제이다. 따라서 위 두 경우를 더해준 값을 DP[n][k]에 저장한다.

 

정리하자면, 점화식은 다음과 같다.

DP[n][k] = (DP[n-1][k] + DP[n-2][k-1]) % P(10억 3)

 

DP 배열의 초기값

 

우선 점화식에 따라서 dp[n][k]를 구하기 위해서는 dp[n-1][k]의 값, dp[n-2][k-1]의 값을 알아야 함을 알 수 있다. 우리는 k = 0, 1일 때의 기본 값을 다음과 같이 설정해 줄 수 있다.

k = 1

우선 k = 1인 경우를 먼저 보면, k = 1이라는 것의 의미는 임의의 n에 대해 n개의 색상 중 1개를 선택하는 경우의 수이다. 이는 무조건 n가지 경우의 수가 나오므로, dp[n][1] = n임을 알 수 있다.

k = 0

k = 0이라는 의미는, 임의의 n에 대해 n개의 색상 중 하나도 선택하지 않는 경우의 수이다. 이는 의미 상으로는 어떤 값으로 초기화를 해야할 지 감이 잡히지 않을 수 있다.

하지만 점화식을 만족시키기 위해서 해당 값은 반드시 1이 되어야 한다. 이는 처음에 그렸던 표를 보면 좀 더 쉽게 이해할 수 있다.

위에서 표만 보자. 표를 보면 알 수 있듯이, dp[n][1] = n을 만족시키기 위해서는 dp[n][0]의 값에 모두 1이 들어가야 함을 알 수 있다.

따라서 다음과 같은 코드를 통해 DP 배열을 초기화 해줄 수 있다.

for (int i = 0; i <= N; i++){
    dp[i][0] = 1; //점화식에 따라
    dp[i][1] = i; //i개의 색상에서 1개를 뽑는 경우의 수는 i가지
}

 

 

DP 배열 채우기

 

만든 점화식을 가지고 DP 배열을 채워보자. 이건 쉽다.

for (int n = 2; n < N; n++){
    for (int k = 2; k <= K; k++){
        dp[n][k] = (dp[n-2][k-1] + dp[n-1][k]) % P;
    }
}

 

마지막 원소는 첫 번째 원소와 인접해 있다

 

이를 잊으면 안 된다. 이 문제에서 주어지는 색상표는 원형이다! 따라서 마지막 원소의 경우에는 점화식을 조금 바꿔주어야 한다.

원래 점화식은 다음과 같다.

DP[n][k] = (DP[n-1][k] + DP[n-2][k-1]) % P(10억 3)

• n번째 색상을 사용하지 않는 경우 + 사용하는 경우
• n-1번째 색상을 사용한 경우 + 사용하지 않 경우

이는 현재 n번째 색상에 대해 n-1번째 색상이 사용되었는지만 비교한다. 하지만 N번째, 즉 마지막 원소는 1번째 색상이 사용되었는지에 대해서도 알아야 한다.

 

즉, 마지막 색상에 대해서는 다음과 같다.

• 마지막 색상를 사용하는 경우
  • 1번째 색상과 N-1번째 색상을 사용하지 않아야 한다
  • 기존에는 N-1번째 색상만 사용하지 않으면 됐기에 dp[n-2][k-1]이었지만, 이번에는 하나 더 추가되었다.
  • 즉, dp[n-3][k-1] + 1이다.
• 마지막 색상을 사용하지 않는 경우
  • 이전과 같다. N-1번째 색상을 사용한 경우를 더해주면 된다.
  • 즉, dp[n-1][k]이다.

위와 같은 과정을 통해 마지막 원소에 대해서는 다음과 같은 코드로 구할 수 있다.

System.out.println((dp[N-3][K-1] + dp[N-1][K]) % P);

---

코드

package ps.ㄱSolving;

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

public class BOJ_G3_2482_색상환 {
    static int N, K;
    static int P = 1000000003;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

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

        //dp
        int[][] dp = new int[N+1][K+1]; //0~N, (첫 번째 원소를 선택하지 않은 경우(0)와 선택한 경우(1))
        for (int i = 0; i <= N; i++){
            dp[i][0] = 1; //점화식에 따라
            dp[i][1] = i; //i개의 색상에서 1개를 뽑는 경우의 수는 i가지
        }
        for (int n = 2; n < N; n++){
            for (int k = 2; k <= K; k++){
                dp[n][k] = (dp[n-2][k-1] + dp[n-1][k]) % P;
            }
        }
        System.out.println((dp[N-3][K-1] + dp[N-1][K]) % P);
    }
}