[BAEKJOON] 2482번 : 색 상 환

문 제

 

소 스  코 드

#include <iostream>

constexpr int MOD	{ 1'000'000'003 };

int dp[1'001][1'001];		// N, K


// i번째 칸을 칠하는 경우	dp[i-2][j-1]
// 안칠 하는 경우			dp[i-1][j]
// N번째 칸의 경우, 
// 칠할 경우 1번 칸을 칠해서는 안되고, N-1번 칸도 칠하면 안되기 때문에, 
// dp[i][j] = dp[i-2][j-1] + dp[i-1][j]

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	int N, K;

	std::cin >> N >> K;
	
	for (int i = 0; i <= N; ++i) {
		dp[i][0] = 1;
		dp[i][1] = i;
	}

	for (int i = 2; i <= N; ++i) {
		for (int j = 2; j <= K; ++j) {
			dp[i][j] = (dp[i - 2][j - 1] + dp[i - 1][j]) % MOD;
		}
	}

	int answer{ (dp[N - 1][K] + dp[N - 3][K - 1]) % MOD };
	std::cout << answer;

}

 

풀 이

 

• 다이나믹 플밍 / 점화식

 

출 력 값

 

 

문 제  출 처

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

2482번: 색상환