난이도가 있는 dp문제다.
언제나 그렇듯이 dp는 테이블로 시작해서 테이블로 끝난다.
dp는 테이블만 잘 설계한다면 물리적으로 내부동작이 어떻게 되든지 상관없이 논리적으로 답이 도출된다.
테이블이 설계가 안된다면 수열을 노가다로 찾아야 하는데 실수할 여지도 많고 시간이 얼마나 걸릴지도 알수 없다.
테이블을 잘 설계하면 이전값들의 결과가 현재값에 영향을 끼쳐야하는 형태가 돼야한다.(끊어지지 않고 이어지는 형태)
서론은 여기까지 하고 이제 이문제를 풀어보자.
일단 d[i][j]는 i개 중에서 j개를 선택하는 경우의 수라고 테이블을 설계했을때
딱 두가지 경우만 생각하면 이문제는 풀린다.
1. 첫번째 색을 포함할 것인가? -> 첫번째를 제외한(이미 뽑았음으로) 나머지 n-1개 중에서 k-1개를 마저 뽑는다.
2. 첫번째 색을 포함하지 않을 것인가? -> 첫번째를 제외한 나머지 n-1개 중에서 k개를 뽑는다.
그래서 점화식을 세우면 d[i][j] = d[i-2][k-1] + d[i-1][k] 이다.
빨간색을 주목하자. 여기서 왜 앞서 말한것과 같이 d[i-1][k-1]이 아니라 d[i-2][k-1]일까?
이 문제는 인접한 색을 뽑으면 안된다는 조건이 있었다. 즉 첫번째 색을 포함하게 된다면 색상환은 원형이기 때문에
맨 마지막색(n번째)은 포함될수 없어서 1을 더 빼줘야 하는것이다.
이렇게 점화식만 논리적으로 빈틈없이 잘세워 준다면 비교적 간결히 문제를 풀수있는것이 dp의 매력이 아닐까 싶다.
#include <bits/stdc++.h>
using namespace std;
int d[1005][1005]; // d[i][j] i개 중에서 j개를 선택하는 경우의 수
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
int n,k;
cin >> n >> k;
for(int i=1; i<=n; i++) d[i][1] = i;
for(int i=2; i<=n; i++){
for(int j=2; j<=k; j++){
if(j > i/2) break;
d[i][j] = (d[i-1][j] + d[i-2][j-1]) % 1000000003;
}
}
cout << d[n][k] << '\n';
}
'CS > 알고리즘 문제풀이' 카테고리의 다른 글
[BOJ 2293] 동전 1 (1) | 2023.12.06 |
---|---|
[BOJ 11055] 가장 큰 증가하는 부분 수열 (1) | 2023.12.04 |
BOJ 복습용 필수문제 큐 + 코테 팁 (0) | 2023.11.28 |
[BOJ 1799] 비숍 (0) | 2023.11.28 |
[BOJ 1600번] 말이 되고픈 원숭이 (1) | 2023.11.21 |