| 시간 제한 | 메모리 제한 |
| 1초 | 128MB |
문제
상근이는 서강 프로그래밍 대회의 문제를 준비해야 한다.
모든 문제의 난이도는 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로 나눈 나머지를 출력한다.
풀이
n번 문제까지 출제 하는 경우를 구했을 때 그 결과로 n + 1번째 문제를 출제하는 방법의 수를 유추할 수 있다. i번째 문제를 선택하는 방법의 수를 dp[i]로 관리해보자. 그런데 조건이 조금 까다롭다. 둘째 줄에 들어오는 입력을 A, 셋째 줄에 들어오는 입력을 B로 받고 i번째 문제를 출제하는 방법을 따져보자.
먼저 i번째 문제를 A[i]에서 출제할 수 있다. 이 경우, 이전 문제를 A, B 어디에서 출제해도 제한이 없다. 따라서 이 경우를 dp[i][0]으로 생각하면 이전의 모든 경우에 A[i]를 곱한 것과 같다.
다음으로 B[i]에서 문제를 출제하는 경우다. B에서 문제를 출제하는 경우를 dp[i][1]로 생각해보자. 이 경우가 약간 복잡한데, B[i]의 문제는 i번째와 i + 1번째 문제로 출제가 가능하므로 dp[i]와 dp[i + 1] 모두에 영향을 준다. 따라서 dp[i][0]을 구성하기 위해서는 dp[i - 1][1]이 먼저 구성되어 있어야 한다. 여기서 작업의 순서가 이렇게 정리된다.
dp[0][0] = 1 → dp[0][1] → dp[1][0] → dp[1][1] → dp[2][0] → ... → dp[i - 1][1] → dp[i][0] → ...
i번째 문제를 B에서 가져오는 방법은 3가지가 있다.
1) 이전 문제를 A에서 출제한 경우, B[i]에서 가져오기
2) 그냥 B[i - 1]에서 가져오기
3) 이전 문제를 B에서 출제한 경우 B[i - 1]에서 출제하기
1), 2)는 A[i]에서 출제하는 것과 비슷하게 처리할 수 있다. 3)만 예외 처리를 해줄 필요가 있는데 이미 B[i - 1]에서 한 문제가 출제 되었으니 이번에 출제할 수 있는 문제의 수가 1 줄어야 한다.
dp[0][0]은 0개의 문제로 0개의 문제를 출제하는 방법의 수 이므로 1가지 가능하도록 초기화 시키고 탐색을 시작한다.
탐색은 1부터 N까지로 먼저 i - 1항의 B에서 출제하는 방법부터 확인하고 i항의 A에서 출제하는 방법을 확인한다.
정답 코드
import sys
input = sys.stdin.readline
def solution():
div = int(1e9 + 7)
N = int(input())
A = [0] + list(map(int, input().split()))
B = [0] + list(map(int, input().split()))
DP = [[0] * 2 for _ in range(N + 1)]
DP[0][0] = 1
for i in range(1, N + 1):
DP[i - 1][1] = (DP[i - 2][0] + DP[i - 2][1]) * B[i - 1]
DP[i - 1][1] %= div
DP[i][0] = (DP[i - 1][0] + DP[i - 1][1]) * A[i]
DP[i][0] += DP[i - 1][0] * B[i - 1]
DP[i][0] += DP[i - 1][1] * (B[i - 1] - 1)
DP[i][0] %= div
print(DP[N][0])
solution()
