[백준] BOJ_2482 - 색상환

1. 문제 정보

• 문제 요약: $N$개의 색상이 원형으로 배치되어 있습니다. 이 중에서 인접하지 않게 $K$개의 색상을 선택하는 경우의 수를 구하는 문제입니다.
  • $N$은 4 이상 1,000 이하의 정수.
    
  • 결과값은 1,000,000,003으로 나눈 나머지를 출력.
    
• 난이도: Gold 3
  
• 링크: 백준 2482번 - 색상환
  

2. 접근 방식

1) 문제의 본질: 선형 vs 원형

가장 먼저 고민해야 할 것은 자료구조의 형태입니다.

• 선형(Linear): 1번과 N번이 떨어져 있습니다. 단순히 앞에서부터 채워나가면 됩니다.
  
• 원형(Circular): 1번과 N번이 인접해 있습니다.
  

이 '연결된 꼬리' 때문에 일반적인 재귀나 순차적 DP를 그대로 적용하기 어렵습니다. 보통 이런 문제는 "케이스를 분리하여 선형으로 환원"하는 것이 정석입니다.

2) 왜 백트래킹(Backtracking)은 안 되는가?

문제의 제약 조건을 봅시다. $N=1000$입니다.

만약 $N=1000, K=500$인 경우, 조합(Combination)의 수는 천문학적인 숫자가 됩니다.

$_{1000}C_{500}$

이는 일반적인 백트래킹($O(2^N)$ 혹은 지수 시간)으로는 절대 시간 내에 풀 수 없습니다. 따라서 중복된 하위 문제(Overlapping Subproblems)를 해결하는 DP가 필수입니다.

3) 점화식 설계

$DP[i][j]$를 $i$개의 색상 중에서 인접하지 않게 $j$개를 고르는 경우의 수라고 정의합시다.

① 기본 점화식 (선형과 동일한 논리)

$i$번째 색상을 기준으로 생각해보면, 두 가지 선택지가 있습니다.

1. $i$번째 색상을 선택하지 않는 경우 ($X$):

   • 나머지 $i-1$개의 색상 중에서 $j$개를 골라야 합니다.
     
   • $\rightarrow DP[i-1][j]$
     

2. $i$번째 색상을 선택하는 경우 ($O$):

   • 인접한 $i-1$번째는 선택할 수 없습니다.
     
   • 따라서 나머지 $i-2$개의 색상 중에서 $j-1$개를 골라야 합니다.
     
   • $\rightarrow DP[i-2][j-1]$
     

$DP[i][j] = DP[i-1][j] + DP[i-2][j-1]$

② 원형 구조의 처리

보통 원형 문제는 "첫 번째를 뽑았을 때"와 "안 뽑았을 때"로 나누어 DP를 두 번 돌리거나 복잡한 처리를 합니다. 하지만, 초기값(Base Case)을 원형의 정의에 맞게 잘 세팅하면 위 점화식을 그대로 사용할 수 있습니다.

• $j=1$일 때 (1개를 고를 때):
  • 원형이든 선형이든 $i$개 중 1개를 고르는 방법은 $i$가지입니다.
    
  • dp[i][1] = i
    
• $i=2, j=1$ (2개 중 1개 선택):
  • 2가지 (dp[2][1] = 2)
    

이 초기값 설정을 통해, 점화식은 $N$까지 순차적으로 돌면서 원형의 제약 조건을 포함한 값을 계산해냅니다. (수학적으로 루카스 수열 등의 성질과 관련이 깊습니다.)

---

3. 코드 구현

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N, K;
    static int[][] dp;
    static final int MOD = 1_000_000_003;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        K = Integer.parseInt(br.readLine());

        // 예외 처리: N개로 인접하지 않게 K개를 고를 수 있는 최대치는 N/2
        if (K > N / 2) {
            System.out.println(0);
            return;
        }

        dp = new int[N + 1][K + 1];
        
        // 초기값 설정
        // 2개 중 1개를 고르는 경우의 수 = 2
        dp[2][1] = 2; 

        for (int color = 3; color <= N; color++) {
            // color개 중 1개를 고르는 경우 = color 가지
            dp[color][1] = color;

            for (int k = 2; k <= K; k++) {
                // 점화식: (이번 색 안 고름) + (이번 색 고름, 바로 앞은 못 고름)
                dp[color][k] = dp[color - 1][k] + dp[color - 2][k - 1];
                dp[color][k] %= MOD; // 모듈러 연산 필수
            }
        }

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

---

4. 회고 및 배운 점

💡 실패 원인 사전 차단

이 문제에서 가장 중요한 판단은 "백트래킹을 배제하는 것"이었습니다.

• 문제에서 $1,000,000,003$으로 나눈 나머지를 요구한다는 것은 결과값이 long 범위도 초과할 만큼 크다는 힌트입니다.
  
• $N=1000$일 때의 탐색 공간은 지수적으로 증가하므로, $O(N \times K)$의 시간 복잡도를 가지는 DP로 접근한 것은 매우 적절한 판단이었습니다.
  

💡 구현 디테일: dp[1][1]의 함정

코드에서 반복문은 color = 3부터 시작합니다.

• dp[1][1]은 초기화되지 않아 0입니다.
  
• 사실 $N=1$일 때 1개를 고르는 것은 1가지지만, 문제 조건에서 $N$은 4 이상이므로 이 부분은 결과에 영향을 주지 않습니다.
  
• 오히려 dp[2][1]=2로 명확히 박아두고, 3부터 루프를 돌린 것이 ArrayIndexOutOfBounds 에러를 피하는 깔끔한 방법이 되었습니다.