알고리즘/백준
[백준] 1563번 개근상
JeongHyeon
2019. 11. 4. 21:55
문제
https://www.acmicpc.net/problem/1563
풀이
dynamic programming / recursion 을 통해 풀이 했습니다.
gCache : day 에 출석, 지각, 결석 횟수 저장
recursion 함수를 통해 저장된 값이 있으면 활용하고 아닌 경우 다음날을 3가지 경우로 분기시켜 진행 시켰습니다.
출석하는 경우 (day + 1, attendance + 1, late, 0)
ㄴ지각하는 경우 (day + 1, attendance, late +1, 0)
결석하는 경우 (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;
}