[백준 5546번] 파스타 (C++)

문제링크 : https://www.acmicpc.net/problem/5546

5546번: 파스타

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair<int, int>

int arr[101];
int dp[101][4][4]; // 날짜, 전날 음식, 현재 음식

int main()
{
    int N, K, result = 0;
    cin >> N >> K;
    for(int i=0; i<K; i++)
    {
        int a, b;
        cin >> a >> b;
        arr[a] = b; //지정된 날짜
    }

    for(int i=1; i<4; i++)
    {
        for(int j=1; j<4; j++)
        {
            if(arr[1] != 0 && arr[1] != i) continue; //지정된 음식 체크
            if(arr[2] != 0 && arr[2] != j) continue;
            dp[2][i][j] = 1;
        }
    }

    for(int i=3; i<=N; i++) //날짜
    {
        for(int j=1; j<4; j++) //현재 음식
        {
            if(arr[i]!=0 && arr[i]!=j) continue; //현재 지정된 음식 체크
            for(int k=1; k<4; k++) //전날 음식
            {
                if(arr[i-1] != 0 && arr[i-1] != k) continue; //전날 지정된 음식 체크
                for(int l = 1; l<4; l++)
                {
                    if(j==k && k==l) continue; //3일 연속 같은 음식인지 체크
                    dp[i][k][j] += dp[i-1][l][k] % 10000; //전날에 해당할 수 있는 케이스들 저장
                }
            }
        }
    }
    for(int i=1; i<4; i++)
    {
        for(int j=1; j<4; j++)
        {
            result += dp[N][i][j];
        }
    }

    cout << result % 10000 ;

    return 0;
}

DP 문제다 

3차원 배열을 이용한 DP문제는 아직 미숙한 것 같다.

처음 dp 배열을 초기화 할때, 날짜에 지정된 음식이 없으면 전부 가능하고, 지정된 음식이 있다면 해당 음식만 체크한다.

 

dp배열이 [N][i][j]인데, N=날짜, i=전날 음식, j=현재 음식이다.

전날 음식에 따라서 현재 음식이 변하기 때문에, 전날 음식에 대해서도 지정된 음식이 있는지 체크를 해줘야 한다.

그리고 3일 연속으로 같은 음식인지를 체크하기 위해 연속된 3값이 동일 한지도 체크한다. (현재, 전날, 전전날)

그리고 현재 날짜에 전날에 올 수 있는 케이스를 각각 저장한다.

 

<예제>
5 3
3 1
1 1
4 2

1일 1번째 파스타 고정
2일 고정 없음
3일 1번째 파스타 고정
4일 2번째 파스터 고정
5일 고정 없음

dp[N][i][j] : N = 현재 날짜, i = 전날 음식, j = 현재 음식

<1일차> 
1번째 파스타 고정
dp[1][0][1] = 1;

<2일차>
전날이 1번째 파스타로 고정
dp[2][1][1] = 1 
dp[2][1][2] = 1
dp[2][1][3] = 1 

<3일차>
1번째 파스타 고정
dp[3][1][1] = dp[2][2][1] + dp[2][3][1] (1일차가 1이기에 dp[2][1][1] 불가능[3일 연속 같음])
dp[3][2][1] = dp[2][1][2] + dp[2][2][2] + dp[2][3][2]
dp[3][3][1] = dp[2][1][3] + dp[2][2][3] + dp[2][3][3]

<4일차>
2번째 파스타 고정
dp[4][1][2] = dp[3][1][1] + dp[3][2][1] + dp[3][3][1] (전날이 1번째 파스타로 고정임)

<5일차>
전날이 2번째 파스타로 고정
dp[5][2][1] = dp[4][1][2] + dp[4][2][2] + dp[4][3][2]
dp[5][2][2] = dp[4][1][2] + dp[4][3][2] (3일차가 2이기에 dp[4][2][2] 불가능[3일 연속 같음])
dp[5][2][3] = dp[4][1][2] + dp[4][2][2] + dp[4][3][2]