백준 2482번 [색상환](C++) -yes6686- 티스토리

백준 문제 풀이: 2482 [색상환]

---

문제 링크: https://www.acmicpc.net/problem/2482

문제 설명:

색상환에 색상 N개가 원형으로 배치되어 있습니다. 이 중 K개의 색상을 고르려 합니다. 단, 인접한 색은 동시에 선택할 수 없습니다. 가능한 경우의 수를 구하는 문제입니다. 결과는 1,000,000,003으로 나눈 나머지를 출력합니다.

---

문제 해결 코드

#include <iostream>
#define MOD 1000000003 
using namespace std;

int dp[1001][1001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, k;
    cin >> n >> k;

    // DP 초기화
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= n / 2; j++) {
            if (j == 1) {
                dp[i][j] = i; // i개의 색 중 하나를 선택하는 경우
            } else {
                dp[i][j] = (dp[i - 1][j] + dp[i - 2][j - 1]) % MOD; 
                // 원소를 선택하지 않은 경우 + 원소를 선택한 경우
            }
        }
    }

    cout << dp[n][k] << '\n';    
    return 0;
}

---

코드 설명

• 핵심 알고리즘: 동적 프로그래밍을 사용하여 색상환에서 K개의 색을 선택하는 경우의 수를 계산합니다. 인접한 색은 선택할 수 없으므로 각 색을 선택했을 경우와 선택하지 않았을 경우를 나누어 점화식을 세웁니다.
• 점화식:
  • dp[i][j] = dp[i-1][j] + dp[i-2][j-1]
  • dp[i-1][j]: 해당 원소를 선택하지 않은 경우
  • dp[i-2][j-1]: 해당 원소를 선택한 경우
• 구현 세부사항:
  • dp[i][j]: i개의 색상 중 j개의 색상을 선택하는 경우의 수
  • j가 1인 경우에는 i개의 색상 중에서 선택할 수 있는 경우의 수는 i
  • K > N/2일 경우는 불가능한 조합이므로 이를 신경쓰지 않아도 됨
• 시간 복잡도: O(n * k)
  • n은 색상 개수
  • k는 선택할 색상의 개수

---

결과

색상환에서 K개의 색상을 선택할 수 있는 경우의 수를 정확히 계산합니다. 동적 프로그래밍과 모듈러 연산을 사용해 효율적으로 문제를 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!