[BOJ] 24464 득수 밥 먹이기

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

24464번: 득수 밥 먹이기

문제

프로젝트 하느라 바쁜 득수는 밥 먹을 시간이 부족하다. 그래서 주로 찾는 식당 네 개 중 하나에서 하루에 한 번 밥을 먹는다. 귀찮으면 굶을 때도 있다.

늘 새로운 느낌을 받고 싶었던 득수는 다음과 같은 규칙으로 다음날 갈 식당을 정한다.

• 첫날에는 굶거나, 임의로 원하는 식당 하나를 골라서 간다.
• 어제 굶지 않았다면, 오늘은 식당을 가지 않아도 된다.
• 어제 식당을 가지 않았다면, 오늘은 식당을 가서 밥을 먹어야 한다.
• 오늘 간 식당은 다음날 가지 않는다.
• 오늘 간 식당과 이웃한 식당은 다음날 가지 않는다.

만약 2번 식당을 오늘 갔다면, 다음날 1, 2, 3번 식당은 가지 않는다. 따라서 새로운 느낌을 받으려면 4번 식당을 가거나 굶어야 한다.

득수가 N일 치 식단표를 만들려고 한다. 위 규칙을 따라 식단표를 만들 때 가능한 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 득수가 만들어야 하는 점심 식단의 총 날짜 N$N$이 입력으로 들어온다. (1≤N≤200000)$(1 \le N \le 200\,000)$ 

 

출력

 N일 치 식단표를 만들 때 가능한 경우의 수를 1000000007로 나눈 나머지를 출력한다.

---

풀이

이 문제를 보고 바로 dp로 풀면 되겠다는 생각을 했다.

dp[i][j] 이중 배열을 선언하고 i는 날짜를 j는 i번째 날의 경우의 수들을 저장하여 풀었다.

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>

#define SWAP(a, b, type) do { \
    type temp; \
    temp = a;  \
    a = b;     \
    b = temp;  \
} while (0)

#define MOD 1000000007
#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

int N;
ll dp[200001][5];

void input() {
    cin>>N;
}

void init() {
}


void solution() {
    dp[1][0]=1;
    dp[1][1]=1;
    dp[1][2]=1;
    dp[1][3]=1;
    dp[1][4]=1;
    
    for(int i=2;i<=N;i++){
        for(int j=0;j<5;j++){
            if(j==0){
                //전날 첫 번째 집에서 밥을 먹은 경우
                dp[i][j]=(dp[i-1][4]+dp[i-1][2]+dp[i-1][3])%MOD;
            }else if(j==1){
                //전날 두 번째 집에서 밥을 먹은 경우
                dp[i][j]=(dp[i-1][4]+dp[i-1][3])%MOD;
            }else if(j==2){
                //전날 세 번째 집에서 밥을 먹은 경우
                dp[i][j]=(dp[i-1][4]+dp[i-1][0])%MOD;
            }else if(j==3){
                //전날 네 번째 집에서 밥을 먹은 경우
                dp[i][j]=(dp[i-1][4]+dp[i-1][0]+dp[i-1][1])%MOD;
            }else{
                //전날 굶은 경우
                dp[i][j]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+dp[i-1][3])%MOD;
            }
        }
    }
    ll ans=0;
    for(int i=0;i<5;i++){
        ans+=dp[N][i];
        ans%=MOD;
    }
    cout<<ans;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}