Problem-Solving/BOJ
[BOJ/백준][Gold4] 1563 : 개근상 (C++)
has2
2020. 12. 20. 21:16
1563번: 개근상
백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독
www.acmicpc.net
[난이도] Gold4
[유형] DP
[풀이]
DP[n][l][a] : 현재 n일이고 총 l일 지각했고, a일 연속으로 결석한 상태일 때 N일까지 개근할 수 있는 경우의 수.
점화식 => DP[n][l][a] = DP[n+1][l][0] 출석한 경우
+ DP[n+1][l+1][0] 지각한 경우 (a가 연속되지 않으므로 초기화)
+ DP[n+1][l][a+1] 결석한 경우 (l은 연속되지 않아도 되므로 유지하고 a+1)
#include <cstdio>
#include <cstring>
int N,dp[1001][4][4],mod=1000000;
int sol(int n,int l,int a){
if(l==2 || a==3) return 0;
if(n==N) return 1;
int& ret =dp[n][l][a];
if(ret!=-1) return ret;
return ret = (sol(n+1,l,0)+sol(n+1,l+1,0)+sol(n+1,l,a+1))%mod;
}
int main(){
scanf("%d",&N);
memset(dp,-1,sizeof(dp));
printf("%d",sol(0,0,0));
}
https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1563.cpp