BOJ 2482번
-
[BOJ] 2482번 - 색상환Algorithm/BOJ 2022. 6. 13. 22:15
[BOJ] 2482번 - 색상환 https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 알고리즘 연속되어 있는 색은 추가가 불가능 단계별 갯수를 세가면서 추가 -> DP DP를 나타낼 때 DP[i][j] 시 i는 색의 갯수 / j는 색을 고를 수 있는 경우이다. 1. i가 1인 경우에는 모두 n의 갯수에 맞추어 증가한다. 2. 후에 i가 2부터는 경우의 수를 나타내다 보면 DP[i][j] = DP[i-1][j-2] + DP[i][j-1] 로 계산식이 되는 것을 알 수 있다...