[C++] 백준 1563번 개근상

n의 날짜가 주어집니다.

각각 출석, 지각, 결석을 할 수 있는데

지각을 2번하거나, 결석을 연속3번하면

개근상을 받지 못합니다.

이 때 개근상을 받을 수 있는 경우의 수를 구하는 문제입니다.

(경우의 수를 100만으로 나눈 나머지를 출력합니다.)

 

memo[지각][결석]으로 값들을 저장했습니다.

출석과 지각, 결석으로 만들 수 있는 경우의 수는

지각 0 결석 0

지각 0 결석 1

지각 0 결석 2

지각 1 결석 0

지각 1 결석 1

지각 1 결석 2 입니다.

 

지각 0 결석 0은

- 지각 0 결석 0 (출석)

- 지각 1 결석 0 (지각)

- 지각 0 결석 1 (결석)

의 3가지 경우의 수를 만들 수 있습니다.

이와 같은 경우의 수를 미리 입력하고

재귀함수를 이용해서 각각의 값들이

더해지면서 풀도록 만들었습니다.

 

#include  
using namespace std; 

int memo[2][3]; // 저장된 값 
int temp[2][3];  // 임시 계산된 값 
int n;              // n일 
      
void insertValue() // temp값을 memo에 삽입  
{                      // temp값을 0으로 초기화 
    memo[0][0] = temp[0][0]; 
    memo[1][0] = temp[1][0]; 
    memo[0][1] = temp[0][1]; 
    memo[0][2] = temp[0][2]; 
    memo[1][1] = temp[1][1]; 
    memo[1][2] = temp[1][2]; 
    for (int i = 0; i < 2; ++i) { 
        for (int j = 0; j < 3; ++j) { 
            temp[i][j] = 0; 
        } 
    } 
} 

void init() // temp배열, memo배열 0으로 초기화 
{ 
    for (int i = 0; i < 2; ++i) { 
        for (int j = 0; j < 3; ++j) { 
            memo[i][j] = 0; 
            temp[i][j] = 0; 
        } 
    } 
} 

void printCount() // 각각의 경우의 수의 합을 구함 
{ 
    int count = 0; 

    for (int i = 0; i < 2; ++i) { 
        for (int j = 0; j < 3; ++j) { 
        count += memo[i][j]; 
        } 
    } 
    count %= 1000000; // 100만으로 나눈 나머지 
    cout << count << endl; 
} 

void remainder() // 100만으로 나눈 나머지 
{ 
    memo[0][0] %= 1000000; 
    memo[0][1] %= 1000000; 
    memo[0][2] %= 1000000; 
    memo[1][0] %= 1000000; 
    memo[1][1] %= 1000000; 
    memo[1][2] %= 1000000; 
} 

void ola(int x) // x번째 날 경우의 수 확인 
{ 
    if (x == n && n!=0) { // n번확인 완료 && n이 0이 아닐때 
        return; 
    } 
    if (n < 1) {           // n이 0이하이면 개근상이 안되는  
        memo[0][0]++; // 경우의 수가 없으므로 1가지 
        return; // 종료 
    } 
    if (x == 0) { // 처음 함수가 실행 됬을때 출석, 지각, 결석에 ++ 
        memo[0][0]++; 
        memo[0][1]++; 
        memo[1][0]++; 
    } 
    else { // 두번 이상 함수가 돌때 출석, 지각, 결석에 대한 경우의수 계산 
        temp[0][0] += memo[0][0]; // 출석 
        temp[1][0] += memo[0][0]; // 지각 
        temp[0][1] += memo[0][0]; // 결석 

        temp[1][0] += memo[1][0]; // 출석 
        //temp[2][0] += memo[1][0]; // 지각 - 지각2번
        temp[1][1] += memo[1][0]; // 결석 

        temp[0][0] += memo[0][1]; // 출석 
        temp[1][0] += memo[0][1]; // 지각 
        temp[0][2] += memo[0][1]; // 결석 

        temp[0][0] += memo[0][2]; // 출석 
        temp[1][0] += memo[0][2]; // 지각 
        //temp[0][3] += memo[0][2]; // 결석 - 결석 연속 3번

        temp[1][0] += memo[1][1]; // 출석 
        //temp[2][0] += memo[1][1]; // 지각 - 지각 2번
        temp[1][2] += memo[1][1]; // 결석 

        temp[1][0] += memo[1][2]; // 출석 
        //temp[2][2] += memo[1][2]; // 지각 - 지각 2번
        //temp[1][3] += memo[1][2]; // 결석 - 결석 연속 3번

        insertValue(); // temp값을 memo에 삽입 
        remainder(); // 100만으로 나누어줌 
    } 

    ola(++x); // ++x번째날에 대한 경우의수 계산 
} 


int main(int argc, char *argv[]) 
{ 
    cin >> n;     // n일  
    init();          // 배열 초기화 
    ola(0);         // 경우의수 함수 
    printCount(); // 총 경우의 수 계산 

    return 0; 
}