[BOJ] 백준 2482 색상환 - Python/Java

문제

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

2482번: 색상환

해설

이 문제에서 중요한 조건은 색상들이 "원형"으로 놓여져있다는 것인데요. 

 

원형 배열에서는 맨 앞의 원소와 맨 마지막 원소가 서로 인접해있기 때문에, 이 둘의 관계를 적절히 처리해주는 것이 문제를 푸는데 핵심적인 열쇠가 됩니다.

 

저는 이 문제를 해결하기 위해 다음의 두 케이스를 나누어 생각하고, 두 케이스에서 구한 답을 총 경우의 수에 더해서 정답을 냈는데요(원형 배열에서 아래와 같이 두 가지 케이스로 나누어 문제를 처리하는 것은 꽤 자주(?) 나오는 테크닉이니 알아두면 좋을 것 같습니다).

 

1) 맨 앞의 색상을 선택하는 경우 -> (n-3, k-1) 선택

2) 맨 앞의 색상을 선택하지 않는 경우 -> (n-1, k) 선택

 

1)번 경우를 고려하면 1번, 2번, 마지막 색상은 선택할 수 없으며 그 나머지 색깔들 중에서 K-1개의 색을 선택하는 문제가 됩니다. 마찬가지로 2)번 경우를 고려하면 1번 색상만 제외한 나머지 색깔 중에서 K개의 색을 선택하는 문제가 됩니다.

 

그리고 1), 2)번의 경우에서 나머지 색상 중에서 K-1개 혹은 K개의 색상을 선택할 때는 "원형이 아닌 직선 배열에서 색상을 뽑는 상황으로 변한다는 점을 알아채야" 합니다. 즉, 1), 2)번 상황에서 제외한 색상들로 인해 절대 직선에서 인접하지 않은 색상들을 뽑아도 절대 이 색상들이 원형으로 이어지지 않는다는 것입니다.

 

따라서, 아래 풀이에서도 확인하실 수 있겠지만 위의 상황을 DP로 처리하기 위해 "N개의 원소가 직선으로 놓인 상황에서 K개를 뽑는" DP 테이블을 만들었습니다. 그리고 실제 정답을 구할 때는 1), 2)번의 두 상황을 이전에 구한 DP에서 가져오기만 하면 됩니다.

 

 

풀이 - 파이썬

n = int(input()) # 색상환에 포함된 색의 개수
k = int(input()) # 선택할 색의 개수

def getBaseDP(n):
    dp = [[0] * (n+1) for _ in range(n+1)]
    dp[1][0] = 1
    dp[1][1] = 1

    for i in range(2, n+1):
        for j in range(1, n+1):
            if j == 1: dp[i][j] = i
            elif i > j: dp[i][j] = dp[i-2][j-1] + dp[i-1][j]
    return dp

# 일직선 상에서 N개 중에 K개를 연속하지 않도록 뽑는 경우의 수
baseDP = getBaseDP(n);

# 원형 모양의 i개의 색깔 중에서 j개를 선택할 수 있는 경우의 수
if k == 1: 
    print(n)
else:
    print((baseDP[n-3][k-1] + baseDP[n-1][k]) % 1000000003)

풀이 - 자바

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

public class B_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());

        // 일직선 상에서 N개 중에 K개를 연속하지 않도록 뽑는 경우의 수
        int[][] baseDP = getBaseDP(n);

        // 원형 모양의 i개의 색깔 중에서 j개를 선택할 수 있는 경우의 수
        if(k == 1) System.out.println(n);
        else System.out.println((baseDP[n-3][k-1] + baseDP[n-1][k]) % 1000000003);
    }

    public static int[][] getBaseDP(int n){
        int[][] dp = new int[n+1][n+1];
        dp[1][0] = 1;
        dp[1][1] = 1;

        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(j == 1) dp[i][j] = i;
                else if(i > j) dp[i][j] = (dp[i-2][j-1] + dp[i-1][j]) % 1000000003;
            }
        }
        return dp;
    }
}