문제 개요
양의 정수 n이 주어졌을 때, 길이가 n인 모든 가능한 출석 기록 중 보상 가능(rewardable)한 기록의 개수를 구하는 것이 이번 문제의 목표입니다. 답이 매우 커질 수 있기 때문에 결과는 10^9 + 7로 나눈 나머지를 반환해야 합니다.
학생 출석 기록 문자열에는 아래 세 가지 문자만 사용할 수 있습니다.
- A : 결석(Absent)
- L : 지각(Late)
- P : 출석(Present)
출석 기록이 보상 가능하려면 다음 두 조건을 모두 충족해야 합니다.
- 결석(A)이 최대 1개 이하여야 합니다.
- 연속된 지각(L)이 최대 2개 이하여야 합니다.
예시
입력이 2라면 출력은 8입니다. 보상 가능한 8가지 조합은 PP, AP, PA, LP, PL, AL, LA, LL이며, A가 두 번 등장하는 AA만 제외됩니다.
풀이 전략: 동적 계획법(DP)
이 문제는 상태를 나누어 관리하는 동적 계획법으로 효율적으로 해결할 수 있습니다. 각 상태는 마지막 글자의 종류와 지금까지 결석(A)이 있었는지 여부에 따라 구분됩니다.
먼저 오버플로우를 방지하기 위해 모듈러 덧셈을 처리하는 add() 함수를 정의합니다. 이 함수는 a와 b를 인자로 받아 ((a mod m) + (b mod m)) mod m 값을 반환합니다.
메인 로직에서는 크기가 n+1인 다섯 개의 배열 p, a, l, ap, al을 선언하고 아래 단계를 따릅니다.
- n이 1이라면 즉시 3을 반환합니다.
- 배열의 초깃값을 설정합니다. p[0]=1, p[1]=1, p[2]=3 / a[0]=1, a[1]=1, a[2]=2 / l[0]=1, l[1]=1, l[2]=3 / ap[0]=1, ap[1]=1, ap[2]=2 / al[0]=1, al[1]=1, al[2]=2
- i를 3부터 n까지 순회하면서 다음 점화식을 적용합니다.
- p[i] = add(add(p[i-1], a[i-1]), l[i-1]) : 현재 자리에 P를 배치하는 경우
- l[i] = add(add(p[i-1], p[i-2]), add(a[i-1], a[i-2])) : 현재 자리에 L을 배치하는 경우 (연속 지각 제한 때문에 직전이 L이라면 그 앞은 P 또는 A여야 함)
- a[i] = add(al[i-1], ap[i-1]) : 현재 자리에 A를 배치하는 경우 (아직 A가 없는 상태에서만 가능)
- al[i] = add(ap[i-1], ap[i-2]) : A 뒤에 L을 배치하는 경우
- ap[i] = add(ap[i-1], al[i-1]) : A 뒤에 P를 배치하는 경우
최종적으로 add(add(p[n], l[n]), a[n])을 반환하면 원하는 정답을 얻을 수 있습니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b){
return ( (a % m) + (b % m) ) % m;
}
int checkRecord(int n) {
vector <int> p(n+1), a(n+1), l(n+1), ap(n+1), al(n+1);
if(n == 1)return 3;
p[0] = 1;
p[1] = 1;
p[2] = 3;
a[0] = 1;
a[1] = 1;
a[2] = 2;
l[0] = 1;
l[1] = 1;
l[2] = 3;
ap[0] = 1;
ap[1] = 1;
ap[2] = 2;
al[0] = 1;
al[1] = 1;
al[2] = 2;
for(int i = 3; i <= n; i++){
p[i] = add(add(p[i-1], a[i-1]), l[i-1]);
l[i] = add(add(p[i-1], p[i-2]),add(a[i-1] , a[i-2]));
a[i] = add(al[i-1], ap[i-1]);
al[i] = add(ap[i-1], ap[i-2]);
ap[i] = add(ap[i-1], al[i-1]);
}
return add(add(p[n], l[n]), a[n]);
}
};
main(){
Solution ob;
cout << (ob.checkRecord(3));
}
실행 결과 확인
입력:
3
출력:
19
위 코드는 각 상태를 선형 시간에 갱신하므로 전체 시간 복잡도는 O(n)이며, n이 클 때도 효율적으로 동작합니다.