[LeetCode] 552. Student Attendance Record II

https://leetcode.com/problems/student-attendance-record-ii/description/?envType=daily-question&envId=2024-05-26

leetcode - Student Attendance Record II

문제 유형 : 다이나믹 프로그래밍

문제 난이도 : Hard

 

문제

An attendance record for a student can be represented as a string where each character signifies whether the student was absent, late, or present on that day. The record only contains the following three characters:

• 'A': Absent.
• 'L': Late.
• 'P': Present.

Any student is eligible for an attendance award if they meet both of the following criteria:

• The student was absent ('A') for strictly fewer than 2 days total.
• The student was never late ('L') for 3 or more consecutive days.

Given an integer n, return the number of possible attendance records of length n that make a student eligible for an attendance award. The answer may be very large, so return it modulo 10^9 + 7.

 

학생의 출석기록은 A, L ,P로 구성된 문자열로 이루어진다.

A는 결석,

L은 지각,

P는 출석을 뜻한다

아래 두 조건을 만족하면 개근상을 받는다:

학생이 2번 미만의 지각을 한 경우

학생이 3연속 이상의 지각을 하지 않은 경우

 

정수 n이 주어진다.

n일동안의 기간에서 개근상을 받는 경우의 수를 구하시오. 수가 클 수 있으니, 1e9 + 7로 나누시오.

 

풀이

dp[i][결석수][연속지각] = i번째 날부터 시작해서, 앞으로 개근상을 받을 수 있는 경우의 수

만약 i > n이면, 유효한 경우이므로 1을 반환한다.

만약 결석 수가 2이상, 또는 연속지각이 3이상이면 0을 반환한다.

만약 dp에 값이 있으면, 그 값을 반환한다.

 

결석 케이스, 지각 케이스, 정상출석 케이스를 각각 구한다.

이 셋을 모두 더하고 1e9+7로 나눈 나머지를 dp테이블에 저장하고 반환한다.

 

코드

C++

class Solution {
private:
    int n;
    int MOD;
public:
    int solve(int day, int absent, int streak, vector<vector<vector<int>>>& dp) {
        if(streak >= 3) return 0;
        if(absent >= 2) return 0;
        if(day > n) return 1;
        if(dp[day][absent][streak] != -1) return dp[day][absent][streak];

        // absent
        int a = solve(day+1, absent+1, 0, dp);

        // late
        int l = solve(day+1, absent, streak+1, dp);

        // present
        int p = solve(day+1, absent, 0, dp);

        return dp[day][absent][streak] = ((a + l) % MOD + p) % MOD;
    }
    int checkRecord(int n) {
        MOD = 1e9 + 7;
        this -> n = n;
        // dp[days][absent][streak]
        vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(2, vector<int>(3, -1)));

        return solve(1, 0, 0, dp);
    }
};