Skip to content

BOJ5546.md

Latest commit

 

History

History
101 lines (84 loc) · 2.36 KB

BOJ5546.md

File metadata and controls

101 lines (84 loc) · 2.36 KB

문제

파스타

문제 원본

문제의 원본은 여기서 확인하세요.

분류

  • 다이나믹 프로그래밍

풀이

dp[i][j][k] 
  * i : i번째 날
  * j : 파스타 종류 (1~3)
  * k : j번 파스타를 연속으로 먹은 k일 수

기본은 모두 0, 미리 예정된 파스타가 있는 경우 해당 파스타에 대한 번호에 대해서만 dp를 채운다.
그 외에는 아래와 같이 dp를 채운다.

for (int j = 1; j <= 3; j++) {
    // 하루 전에 먹은 파스타와 같은 종류인 경우 ( 2일 연속 )
    if (i == j) {
        dp[d][i][2] = dp[d - 1][j][1];
    }
    // 처음 먹는 경우
    else {
        dp[d][i][1] += dp[d - 1][j][1] + dp[d - 1][j][2];
        dp[d][i][1] %= MOD;
    }
}

전체 소스 코드

#include <iostream>
#define MOD 10000

using namespace std;

// default 0
int dp[101][4][3];
int schedule[101];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < k; i++) {
        int day, taste;
        cin >> day >> taste;
        schedule[day] = taste;
    }

    // 첫째날 스케쥴이 있는 경우 해당 종류의 값만 초기화
    if (schedule[1]) {
        dp[1][schedule[1]][1] = 1;
    }
    // 스케쥴이 없는 경우
    else {
        dp[1][1][1] = 1;
        dp[1][2][1] = 1;
        dp[1][3][1] = 1;
    }


    for (int d = 2; d <= n; d++) {
        for (int i = 1; i <= 3; i++) {
            // 스케쥴이 있는 경우 지정된 종류에 대한 dp만 채운다.
            if (schedule[d] && i != schedule[d]) {
                continue;
            }

            for (int j = 1; j <= 3; j++) {
                // 하루 전에 먹은 파스타와 같은 종류인 경우 ( 2일 연속 )
                if (i == j) {
                    dp[d][i][2] = dp[d - 1][j][1];
                }
                // 처음 먹는 경우
                else {
                    dp[d][i][1] += dp[d - 1][j][1] + dp[d - 1][j][2];
                    dp[d][i][1] %= MOD;
                }
            }
        }
    }


    // n일차에 모든 종류에 대해 처음 먹는 경우, 2일 연속 먹는 경우의 수를 다 더한다.
    int result = 0;
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 2; j++) {
            result += dp[n][i][j];
        }
    }
   
    cout << result % MOD;
    return 0;
}