[Algorithm]Baekjoon 1563번 :: 개근상

https://www.acmicpc.net/problem/1563

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
const int mod = 1000000;
int n;
int dp[1001][3][4] = { 0 };
 
 
int DFS(int index, int lateCount, int absentCount)
{
    if (index == n)
    {
        if (lateCount < 2 && absentCount < 3)
        {
            return 1;
        }
    }
 
    if (lateCount >= 2 || absentCount >= 3) // 이미 개근상을 못받기때문에 더 진행할이유없음.
    {
        return 0;
    }
 
    int& result = dp[index][lateCount][absentCount];
    if (result != -1) return result;
 
    int attendance = DFS(index + 1, lateCount, 0) % mod; // 출석
   int late = DFS(index + 1, lateCount + 1, 0) % mod; // 지각
   int absent = DFS(index + 1, lateCount, absentCount + 1) % mod; // 결석
 
    return result = (attendance + late + absent) % mod;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n; 
 
    memset(dp, -1, sizeof(dp));
 
    cout << DFS(0, 0, 0);
}

 

예전에 풀었었던 문젠데, 그때는 자력으로 풀지못하고 다른사람 Bottom-Up방시의 풀이를 보고 얼추 이해하고 넘어갔었다.

그러다가 solved.ac에서 dp카테고리 문제를 쭉 풀면서 다시 이 문제를 만나게 됐고, 그때 못풀었기 때문에 지금 풀 수 있는지 체크하기 위해 다시 풀었다.

 

결과적으로 다시 풀 수 있었다. Top-Down방식으로의 풀이가 머리속에 좀 더 이해하기가 쉬워서 Top-Down으로 풀어봤다.

먼저 각 차례마다 세가지의 선택지가 주어진다.

출석을 하든, 지각을 하든, 결석을 하든.

 

쭉 분기점마다 갈라지면서 지각, 결석 카운팅을 할건데 지각을 2번이상 하거나 결석을 3번 이상'연속으로' 할 경우, 개근상을 받지 못하기 때문에 더이상 탐색을 할 필요없다.

그렇기 때문에 34번째라인처럼 그냥 바로 탐색을 종료시켜버린다.

 

그리고 결석같은경우는 3번 '연속'이라는 조건이 붙기때문에, 출석을하거나 지각을하면 결석카운팅은 다시 0으로 초기화된다는것을 잊지말자.

 

각 차례마다 지각,결석카운팅의 값이 해당 차례까지의 루트가 독립적이라는것을 표현해줄 수 있다.

그러므로 dp[차례][지각횟수][결석횟수] 가 dp테이블이 된다.

 

독립적이다라는게 무슨말이냐면, LOO랑 OOL이랑 서로 다른루트로 취급되게 탐색이 진행될 수 있다는 것이다.

각 루트의 첫번째차례값은 

LOO == dp[1][1][0]

OOL == dp[1][0][0]     이므로 서로 다른 테이블에 값이 업데이트된다.