백준 2482번 - 색상환

문제

백준 2482번 - 색상환

---

아이디어

만약 N개의 색 중에서 N번째 색을 선택했다면 1번째와 N-1번째 색은 선택할 수 없다. 남은 색 2번째에서 N-2번째 중에 k-1개를 고르는 경우를 알아야 한다.

그리고 N번째 색을 선택하지 않았다면 1번째부터 N-1번까지의 색 중에서 k개를 고르는 경우를 알아야 한다.

즉 DP를 통해서 해결할 수 있다.

1. dp 배열 초기화

int[][] dp = new int[n + 1][k + 1];

for (int i = 1; i <= n; i++) {
    dp[i][0] = 1;   //i개 중에 0개
    dp[i][1] = i;   //i개 중에 1개
}

• dp[n][k]는 n개의 색중에 인접하지 않은 k개를 고르는 경우의 수를 의미한다.
• 0개를 고르는 것과 1개만 고르는 경우는 경우의 수가 각각 1개와 i개인 것이 자명하므로 이 조건들은 초기화할 수 있다.

2. 점화식으로 dp 배열 채우기

for (int i = 4; i <= n; i++) {  //i개 중에
    for (int j = 2; j <= k; j++) {  //j개
    
        if (j > i / 2) break;
        
        dp[i][j] = dp[i - 2][j - 1] + dp[i - 1][j];
        dp[i][j] %= 1_000_000_003;
    }
}

System.out.println(dp[n][k]);

• N번째 색을 선택한 경우(dp[i-2][j-1])와 N번째 색을 선택하지 않은 경우(dp[i-1][j])를 더해준다.
• 만약 선택한 개수가 색 개수의 절반을 넘으면(if(j > i / 2)) 절대 인접하지 않고 고를 수 없게 된다.

---

예상 시간 복잡도

• 예상 시간 복잡도 : O(NK)

---

코드 구현 - 자바

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

public class BJ_2482 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int k = Integer.parseInt(br.readLine());

        int[][] dp = new int[n + 1][k + 1];

        for (int i = 1; i <= n; i++) {
            dp[i][0] = 1;   //i개 중에 0개
            dp[i][1] = i;   //i개 중에 1개
        }

        for (int i = 4; i <= n; i++) {  //i개 중에
            for (int j = 2; j <= k; j++) {  //j개

                if (j > i / 2) break;

                dp[i][j] = dp[i - 2][j - 1] + dp[i - 1][j];
                dp[i][j] %= 1_000_000_003;
            }
        }

        System.out.println(dp[n][k]);
    }
}

코드 구현 - 파이썬

n = int(input())
k = int(input())

dp = [[0] * (k + 1) for _ in range(n + 1)]

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

for i in range(4, n + 1):
    for j in range(2, k + 1):

        if j > i / 2:
            break

        dp[i][j] = dp[i - 2][j - 1] + dp[i - 1][j]
        dp[i][j] %= 1_000_000_003

print(dp[n][k])