[ BOJ 백준 2482번 - 색상환 ] 해설 및 코드

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

 

 

목적

주어진 정수 N과 K에 대하여, N개의 색으로 구성되어 있는 색상환 (N색상환)에서 어떤 인접한 두 색도 동시에 선택하지 않으면서 서로 다른 K개의 색을 선택하는 경우의 수를 구하자.

접근법

1. s[i][j][k]를 i번째 색을 선택(j==1)하거나 미선택(j==0)할 때, k개의 색을 선택하는 경우의 수라고 가정한다. 그러면 s[i][0][k]는 s[i-1][1][k] + s[i-1][0][k] 이고, s[i][1][k]는 s[i-1][0][k-1] 이다.

 

2. 마지막 n번째는 1번째 선택에 따라서 결정되므로 애초에 배열을 두종류로 나누어 처리한다. 하나는 1번째 타일이 선택된 경우, 다른 하나는 1번째 타일이 선택되지 않은 경우. 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
 
const int MOD=1e9+3;
int n,k,s[1001][2][501],t[1001][2][501];
 
int main(){
    cin>>n>>k;
    if((n+1)/2<k){
        cout<<0;
        return 0;
    }
    s[2][0][0]=s[2][1][1]=t[2][0][1]=1;
    f(i,3,n){
        int tmp=n/2+1;
        s[i][0][0]=s[i-1][0][0];
        t[i][0][0]=t[i-1][0][0];
        f(j,1,tmp){
            s[i][0][j]=(s[i-1][0][j]+s[i-1][1][j])%MOD;
            s[i][1][j]=s[i-1][0][j-1];
            t[i][0][j]=(t[i-1][0][j]+t[i-1][1][j])%MOD;
            t[i][1][j]=t[i-1][0][j-1];
        }
    }
    cout<<((long long)s[n][0][k]+s[n][1][k]+t[n][0][k])%MOD;
    return 0;
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.