[BAEKJOON] 1563 개근상

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> using namespace std; int n; vector<vector<vector<int>>>dp(1001, vector<vector<int>>(3, vector<int>(4,-1))); /* 지각 2번 || 결석 3번 연속이면 안됨 */ int Check_Attendance(int attendCnt, int lateCnt, int absentCnt) { if (absentCnt >= 3 || lateCnt >= 2) return 0; if (attendCnt == n) return 1; int&ret = dp[attendCnt][lateCnt][absentCnt]; if (ret != -1) return ret; return ret = (Check_Attendance(attendCnt + 1, lateCnt, 0) + Check_Attendance(attendCnt + 1, lateCnt + 1, 0) + Check_Attendance(attendCnt + 1, lateCnt, absentCnt + 1)) % 1000000; } int main() { scanf("%d", &n); printf("%d", Check_Attendance(0, 0, 0)); return 0; }

삼중 배열을 사용하는 것에 너무 두려움을 가지지 말자!

처음에 if 문 두개를 바꿔써서 더 많은 경우의 수가 나왔다

attendCnt로 return1을 하기 전에

absentCnt와 lateCnt가 조건에 맞는지 확인해야한다.