백준 1563번 개근상

문제 링크입니다: https://www.acmicpc.net/problem/1563

매우 쉬운 DP 문제였습니다.

0일부터 시작해서 다음날 출석, 결석, 지각하는 3가지의 경우의 수를 고려해주면 되는 문제였습니다.

주의할 점은 3번 연속 결석해야지 개근상이 아니므로 출석과 지각하는 날에는 결석 횟수를 0으로 초기화 해줘야합니다!

그런데 무슨 학교가 결석보다 지각을 더 문제 삼는지 모르겠습니다...

#include <iostream>

#include <string>

#include <cstring> //memset

using namespace std;

 

const int MOD = 1000000;

const int MAX = 1000 + 1;

 

int N;

int cache[MAX][MAX][3][2]; //길이, 출석, 결석 연속, 지각

 

int fullAttendance(int days, int attend, int absent, int late)

{

        //기저 사례

        if (absent == 3 || late == 2)

                 return 0;

        if (days == N) //개근상 조건

                 return 1;

 

        int &result = cache[days][attend][absent][late];

        if (result != -1)

                 return result;

       

        //일수, 출석, 결석, 지각

        //연속 결석 아니면 결석은 0

        result = fullAttendance(days + 1, attend + 1, 0, late) + fullAttendance(days + 1, attend, absent + 1, late) + fullAttendance(days + 1, attend, 0, late + 1);

        result %= MOD; //MOD로 나누기

        return result;

}

 

int main(void)

{

        cin >> N;

 

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

 

        cout << fullAttendance(0, 0, 0, 0) % MOD << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~