1744 - 개근상

N일동안의 출석 기록은 OOOO와 같이 길이 N으로 표현될 수 있습니다.

각 위치가 의미하는 것은 i일 째의 기록을 의미합니다. 즉, 각 위치는 1일 째, 2일 째.. 와 같죠.

우선 전탐색을 생각해봅시다.

출석(O) / 지각(L) / 결석(A). 이렇게 3가지로 나누어 지는데, 각 날짜에 대해서 3가지 가능성을 모두 검토하면 $3^N$ 이라는 지수 시간이 걸리겠네요.$3^{}$이라는 어마어마한 시간이 걸리겠네요.

하지만 모든 가능성을 검토해야하는건 사실이므로 소스를 짜봅시다.

대충 중요한 동작 부분만 의사코드로 작성해본다면

f(O, L, A){
    if(O+L+A > N) return 0;    // 모든 출결사항의 기록. 즉, O+L+A 는 기록된 날짜 수와 같습니다.
    if(O+L+A == N-1) return 1; // 마지막 날까지 기록을 모두 확인했다면 한 가지 경우의 수로 취급합니다.

    return f(O+1, L, A)
           + f(O, L+1, A);
           + f(O, L, A+1);
}

이렇게 작성할 수 있겠네요. 하지만 문제를 보면 지각을 두 번 이상 했거나, 결석을 세 번 연속으로 한 사람은 제외 한다고 합니다.

그럼 지각이 두번 이상인 것은 어떻게 확인할까요?

f(O, L, A){
    if(O+L+A > N || L >= 2) return 0; // 지각이 두 번이상 체크되면 경우의 수로 취급하지 않음.
    if(O+L+A == N-1) return 1;

    int ret = 0;
    ret += f(O+1, L, A)
    ret += f(O, L+1, A);
    ret += f(O, L, A+1);
}

문제는 결석의 세 번 연속 등장을 어떻게 구분하는가 입니다. 방법은 간단합니다. 결석이 등장하지 않을 때는 (즉, 출석이나 지각인 경우에는) 결석의 횟수를 0으로 하면 됩니다. 대신 이렇게 되는 경우 O+L+A == N 의 공식이 무너지게 되므로, 날짜 수를 별도로 세어주도록 해야합니다.

f(O, L, A, days){
    if(days > N || L >= 2 || A >= 3) return 0; // 결석이 3번 이상 체크되면 경우의 수로 취급하지 않음.
    if(days == N-1) return 1;

    int ret = 0;
    ret += f(O+1, L, 0, days+1); // 연속이 끊김
    ret += f(O, L+1, 0, days+1); // 연속이 끊김
    ret += f(O, L, A+1, days+1);
}

이 함수를 단순히 메모이제이션하기만 해도 정답이지만, 메모리를 엄청 잡아 먹을것입니다.

현재까지의 코드는 분명 중복되는 부분이 있습니다. 조금만 더 생각해보신다면 중복을 제거하여 효율을 높일 수 있습니다.