[BOJ/백준][Gold4] 1563 : 개근상 (C++)

www.acmicpc.net/problem/1563  

1563번: 개근상

 

[난이도] 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