[BOJ] 백준 2482 색상환 (문제 설명, 코드, C++)

• 문제 설명
• 해결 과정
• 코드 전문

 

문제 설명

 

 

본 문제는 백준의  2482번 색상환 문제입니다.

 

순환구조의 배열에서 각 원소들이 서로 이웃하지 않게끔, 총 n개의 원소 중에 k를 고를 수 있는 경우의 수를 찾는 문제입니다.

 

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

 

 

 

해결 과정

 

 

핵심 아이디어는 첫 원소와 마지막 원소를 둘 다 고려해야할 때를 제외하면

순환적인 구조에서 벗어날 수 있다는 것 입니다. 

그렇기에 시작 원소부터 끝 원소 전까지 반복을 통해 경우를 찾을 수 있습니다.

 

i 번째 원소를 보고 j개 원소를 뽑아야한다면

i 번째 원소를 뽑을 경우 ) dp[i - 2][j - 1]  (i를 뽑았으니 자신을 빼야하고, 자신 이전의 원소는 뽑을 수 없기에 i에 2를 뺍니다)

i 번째 원소를 뽑지 않을 경우 ) dp[i - 1] [j] (i를 뽑지 않았으니 자신 이전의 원소도 뽑을 수 있습니다. i에 1을 뺍니다.)

dp[i][j] = dp[i - 2][j - 1] + dp[i - 1] [j] 이라고 나타낼 수 있습니다.

 

 

이후 첫 번째 원소와 마지막 원소(n)를 포함하는 범위의 경우

마지막 원소(n)를 보고 k개 원소를 뽑아야한다면

마지막 원소를 뽑을 경우 ) dp[n - 3][k - 1] (자신을 뽑았고 자신의 바로 이전, 바로 이후는 뽑을 수 없기에 n에 3을 뺍니다.)

마지막 원소를 뽑지 않을 경우 ) dp[n - 1] [k] (자신을 뽑지 않았기에 바로 이전의 경우를 가져오면 됩니다.)

dp[n][k] = dp[n - 3][k - 1] + dp[n - 1] [k] 이라고 나타낼 수 있습니다.

 

 

 

코드 전문

 

 

#include <iostream>
#include <algorithm>

using namespace std;

const int MOD = 1'000'000'003;
int n, k;
int dp[1002][1002];

int main() {
    cin >> n >> k;

    for (int i = 0; i < 1002; ++i) {
        dp[i][0] = 1;  // 뽑아야할 게 0이라 함은 이 경우의 수가 옮음을 나타내니 1
        dp[i][1] = i;  // dp의 인덱스 i가 1일 때 초기화됨. 고로 아래 반복문에서 i는 2부터 시작.
    }

    for (int i = 2; i < n; ++i) {  // i는 n이전까지 n까지하면 순환을 고려하지 않은 답이 생깁니다.
        for (int j = 2; j <= k; ++j) {
            dp[i][j] = (dp[i - 2][j - 1] + dp[i - 1][j]) % MOD;
        }
    }
    
    int ans = ((dp[n - 3][k - 1] + dp[n - 1][k]) % MOD);
    cout << ans;
}

 

 

 

 

느낀 점 (잡설 99% , 배운점 1%(많은 편))

 

 

꽤나 어려운 문제였습니다. 처음엔 되게 복잡하게 접근했었는데.. 어찌어찌 해결해냈습니다.

다른 알고리즘 기법들도 굉장하지만 특히 DP는 할 때마다 사고가 확장됨을 느낄 수 있습니다. 체감이 됩니다.

마치 중량을 칠 때마다 다음 더 횟수를 늘릴 수 있다던가 중량을 조금 더 늘릴 수 있게 된다던가.

 

그리고 이렇게 공부한 부분을 글로 남긴다는 것도 생각을 다시 정리하는데 있어 정말 중요한 시간이란걸 다시 한 번 

깨달았습니다. 감사합니다.

 

 

 

 

 

 

 

긴 글 읽어주셔서 감사합니다. 

부족한 점이 있다면 부디 알려주시면 감사하겠습니다.