[BAEKJOON] 2854. 문제 출제

문제 :

상근이는 서강 프로그래밍 대회의 문제를 준비해야 한다.

모든 문제의 난이도는 1과 N사이의 자연수로 표현할 수 있다. 하지만, 어떤 문제는 난이도를 정확하게 결정할 수 없는 경우도 있다. 따라서, 상근이는 문제의 난이도를 숫자 하나 또는 연속한 두 수로 표현하기로 했다. 예를 들어, 어떤 문제의 난이도는 3 또는 4가 될 수 있다.

올해 대회는 총 N문제가 필요하다. 상근이는 각 난이도에 해당하는 문제를 한 문제씩 내기로 했다. 당연하겠지만 같은 문제를 두 번 낼 수는 없다.

이때, 문제를 고르는 경우의 수를 구하는 프로그램을 작성하시오. 어떤 난이도에 해당하는 문제가 다른 경우에 두 방법이 서로 다른 경우이다.

정답이 매우 커질 수 있으므로 경우의 수를 1,000,000,007로 나눈다.

입력 :

첫째 줄에 N (2 ≤ N ≤ 100,000)이 주어진다.

둘째 줄에는 109를 넘지 않는 N개의 정수가 주어진다. i번째 수는 난이도가 i인 문제의 개수이다.

셋째 줄에는 109를 넘지않는 N-1개의 정수가 주어진다. i번째 수는 난이도가 i 또는 i+1인 문제의 개수이다.

출력 :

첫째 줄에 문제를 고를 수 있는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

풀이 :

DP에 워낙 약한지라 메모이제이션을 생각해내는 것 까지도 조금 시간이 걸린 문제였다.

문제는 난이도가 겹치는 문제가 있기 때문에 매번 해당하는 난이도 문제를 선택할 경우일 때 마다 난이도가 고정된 문제를 택할 것인지, 난이도가 i-1 ~ i에 해당하는 문제를 고를 것인지, i ~ i+1 난이도에 해당하는 문제를 고를것인지 세 가지 경우로 나누어 볼 수 있다.

따라서 dp 배열을 3개의 행을 가진 2차원 배열로 정리하여 각 경우의 수를 나뉘어서 메모이제이션을 실행해주어야 했다.

• 메모이제이션 점화식

dp[0][i] = (dp[0][i - 1] + dp[1][i - 1] + dp[2][i - 1]) * def[i] % DVD;  // 고정 난이도 문제 택한 경우
dp[1][i] = ((dp[0][i - 1] + dp[1][i - 1] + dp[2][i - 1]) * undef[i - 1] - dp[2][i - 1]) % DVD; // (i-1) ~ i 난이도
dp[2][i] = (dp[0][i - 1] + dp[1][i - 1] + dp[2][i - 1]) * undef[i] % DVD;  // i ~ (i+1) 난이도

이렇게 점화식을 세워주면 손쉽게 경우의 수를 구해볼 수 있다. 다만 주의해줄 점은 마지막에 답을 출력해 줄 때에도 문제에서 주어진 수로 나눈 나머지를 출력해 주어야 한다.. 이 부분을 실수하여 틀리게 결과가 나오는 경우가 있었다.. 주의하자!

코드 :

#include <iostream>

#define ll long long
#define DVD 1000000007

using namespace std;
ll *dp[3];
int *def, *undef;

void fillDpArray(int n) {
    dp[0][0] = def[0];
    dp[2][0] = undef[0];
    for (int i = 1; i < n; i++) {
        dp[0][i] = (dp[0][i - 1] + dp[1][i - 1] + dp[2][i - 1]) * def[i] % DVD;
        dp[1][i] = ((dp[0][i - 1] + dp[1][i - 1] + dp[2][i - 1]) * undef[i - 1] - dp[2][i - 1]) % DVD;
        dp[2][i] = (dp[0][i - 1] + dp[1][i - 1] + dp[2][i - 1]) * undef[i] % DVD;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, i;
    cin >> n;
    def = new int[n];
    undef = new int[n]{0};
    for (i = 0; i < 3; i++)
        dp[i] = new ll[n]{0};
    for (i = 0; i < n; i++)
        cin >> def[i];
    for (i = 0; i < n - 1; i++)
        cin >> undef[i];
    fillDpArray(n);
    cout << (dp[0][n - 1] + dp[1][n - 1] + dp[2][n - 1]) % DVD << '\n';
    return 0;
}