[Java/투포인터] 백준 2482. 색상환

🤔 Intuition

어려웠다. 자력으론 못풀었다. 해석을 참고했다.

 

이 문제는 조합 공식 아이디어를 DP 로직에 적용해보는 게 첫 번째였다. 근데 이게 다가 아니였다.

 

가장 중요했던 건, 기본적으로 DP 배열을 채워넣을 때와 정답을 뽑을 때에 사용되는 점화식을 다르게 세워야 한다는 것이었다.

 

처음에 DP 배열을 기록할 때에는 마치 색상환이 원형 구조가 아니라 선형 구조인 것처럼 고려해야 한다. 이제부터 이게 무슨 말인지 설명하겠다.

 

이 문제는 i번째 인덱스의 색상을 골랐을 때 i-1번째와 i+1번째를 선택하지 않아야 하는데, 이를 고려하는 점화식은 다음과 같다.

DP[N][K] = DP[N-3][K-1] + DP[N-1][K];

 

N개의 숫자 중 K개를 고르는 경우의 수를 구하기 위해서,

1. DP[N-3][K-1] : i번째 색상을 골랐다면 i-1, i, i+1 번째 색상을 제외한 색상들 중에서 K-1개를 고르는 경우의 수
2. DP[N-1][K] : i번째 색상을 고르지 않았다면 i번째 색상을 제외한 색상들 중에서 K개를 고르는 경우의 수

두 가지 경우를 더해줘야 할 것이다.

 

근데, 이를 DP 배열을 채워줄 때 활용하게 되면 공백이 중복되면서 모든 경우를 셀 수 없게 된다. 따라서 실제 DP 배열을 채워넣을 때에는 i번째 색상을 골랐을 경우에는 원형이 아닌 선형 구조인 것 처럼 i, i+1번째 색상을 제외하고 K-1개를 고르는 경우의 수로 계산해줘야 각 (n,k) 쌍에 대하여 공백이 중복되지 않고 모든 경우의 수를 셀 수 있게 된다.

 

다만, 정답을 출력할 때에는 이게 원형 구조임을 고려하여 위에서 소개한 점화식을 이용하여 정답을 도출해야 함에 유의해야 한다.

 

개인적으로 이 문제의 포인트는, DP 문제라기보단, "조합 경우의 수를 구하는 로직을 구성할 때 얼마나 엄밀하고 유연하게 사고할 수 있는지" 인 것 같다. DP는 그냥 얹은 느낌... 아 어렵다~~~~~~~~~

🔎 Algorithm & Complexity

* @algorithm dp
* @time O(N*K) ; N x K 배열을 메모이제이션으로 채워나가는 로직 -> 156 ms
* @memory O(N*K) ; N x K 배열 이용 -> 18200 KB

👨🏻‍💻 Logic

위에서 설명을 충분히 한 것 같아서 시뮬레이션 서술은 생략한다.

 

한가지, dp[i][0] = 1을 추가해주지 않으면 정답을 얻어낼 수 없음 또한 주의해야 한다. 이는 우리의 점화식 논리상 필요한 설정이라, K의 최소값인 1이 주어졌을 때 정답을 뽑아내기 위해 필요하다. (내가 실수해서 첨부)

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

public class Main {
    private static int N, K;
    private static int[][] dp;
    private static final int INF = -1;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        K = Integer.parseInt(br.readLine());
        dp = new int[N+1][N+1];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                dp[i][j] = INF;
            }
        }

        for (int i = 1; i <= N; i++) {
            dp[i][1] = i;
            dp[i][0] = 1;
        }

        go(N, K);
        int ans = (dp[N-3][K-1] + dp[N-1][K])  % ((int) 1e9 + 3);
        System.out.println(ans);
    }

    private static int go(int i, int j) {
        if (i <= 0 || j <= 0) {
            return 0;
        }
        if (dp[i][j] != INF) {
            return dp[i][j];
        }
        return dp[i][j] = (go(i - 2, j - 1) + go(i - 1, j)) % ((int) 1e9 + 3);
    }
}