https://www.acmicpc.net/problem/1563
1563번: 개근상
백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독
www.acmicpc.net
점화식 구하는게 좀 복잡할 수도 있는 dp문제입니다.
문제를 풀고나서 다른분들의 풀이를 보니 3차원배열을 사용하셨던데 저는 2차원 dp배열로 해결하였습니다.
우선 이 문제는 지각을 두 번 이상 하거나, 결석을 세 번 연속으로 하는 경우를 제외한 모든 경우의 수를 구해야합니다.
손으로 직접 그려본 후에 점화식을 찾았습니다.
dp[N][start] : 학기 첫날(start)이 출석 / 지각 / 결석일 때 N번째 날의 경우의 수
[0] [1] [2] sum
N = 1 1 1 1 3
N = 2 3 2 3 8
N = 3 8 4 7 19
N = 4 19 7 17 43
N = 5 43 13 38 94
N = 6 94 24 82 200
dp[N][0] : 첫날이 출석인 경우의 수
-> dp[N - 1][0] + dp[N - 1][1] + dp[N - 1][2]
dp[N][1] : 첫날이 지각인 경우의 수
-> dp[N - 1][1] + dp[N - 2][1] + dp[N - 3][1]
dp[N][2] : 첫날이 결석인 경우의 수
-> dp[N - 1][0] + dp[N - 1][1] + dp[N - 2][0] + dp[N - 2][1]
출력은 dp[N][0 ~ 2]를 더해 1000000으로 mod연산한 값을 출력해주시면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include <iostream>
#define MOD 1000000
using namespace std;
int dp[1001][3];
int N;
void init() {
dp[0][1] = 1;
dp[1][0] = 1;
dp[1][1] = 1;
dp[1][2] = 1;
dp[2][0] = 3;
dp[2][1] = 2;
dp[2][2] = 3;
for (int i = 3; i <= 1000; i++) {
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD;
dp[i][1] = (dp[i - 1][1] + dp[i - 2][1] + dp[i - 3][1]) % MOD;
dp[i][2] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 2][0] + dp[i - 2][1]) % MOD;
}
}
void input() {
cin >> N;
cout << (dp[N][0] + dp[N][1] + dp[N][2]) % MOD << '\n';
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
init();
input();
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 2186 문자판 (0) | 2021.06.19 |
|---|---|
| boj 13325 이진 트리 (0) | 2021.06.18 |
| boj 10800 컬러볼 (0) | 2021.04.09 |
| boj 12869 뮤탈리스크 (0) | 2021.04.04 |
| boj 1520 내리막 길 (0) | 2021.03.28 |