[백준] 1563번 개근상

문제

https://www.acmicpc.net/problem/1563

 

풀이

dynamic programming / recursion 을 통해 풀이 했습니다.

gCache : day 에 출석, 지각, 결석 횟수 저장

recursion 함수를 통해 저장된 값이 있으면 활용하고 아닌 경우 다음날을 3가지 경우로 분기시켜 진행 시켰습니다.

1. 출석하는 경우 (day + 1, attendance + 1, late, 0)

2. ㄴ지각하는 경우 (day + 1, attendance, late +1, 0)

3. 결석하는 경우 (day +1, attendance, late, absent+1)

    

소스코드

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_N = 1000 + 1;
const int MOD = 1000000;

int gCache[MAX_N][MAX_N+1][3][4]; // day, 출석, 지각, 결석
int n;

int solution(int day, int attendance, int late, int absent){

    if(late >= 2 || absent >= 3){
        return 0;
    }

    if(day == n)
        return 1;

    int &ret = gCache[day][attendance][late][absent];
    if(ret >= 0)
        return ret%MOD;

    ret = 0;
    
    ret += solution(day + 1, attendance + 1, late, 0)%MOD + solution(day + 1, attendance, late +1, 0)%MOD + solution(day +1, attendance, late, absent+1)%MOD;

    return ret%MOD;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;

    memset(gCache, -1, sizeof(gCache));

    cout << solution(0,0,0,0) << "\n";

    return 0;
}