CSES 3. Array Description (1746)

출처: https://cses.fi/problemset/task/1746

---

문제 설명

You know that an array has n integers between 1 and m, and the difference between two adjacent values is at most 1.

Given a description of the array where some values may be unknown, your task is to count the number of arrays that match the description.

입력  

The first input line has two integers n and mm: the array size and the upper bound for each value.

The next line has n integers x_1,x_2,…,x_n : the contents of the array. Value 0 denotes an unknown value.

출력 

Print one integer: the number of arrays modulo 10^9+7.

입력 예

3 5
2 0 2

출력 예

3

Explanation: [2,1,2], [2,2,2] , and [2,3,2]

제약조건

• 1 <= N <= 10^5
• 1 <= M <= 100
• 0 <= x_i <= M 

---

문제 풀이 

배열에서 어떤 위치의 숫자는 바로 전 위치의 숫자 값에 따라서 결정된다(+1, -1, 0). 이렇게 가능한 경우의 배열을 x_0 부터 x_n-1까지 계속해서 더해서 만든다. 단, 이렇게 더하는 과정에 커지는 숫자는 modulo 연산으로 일정하게 만든다.

프로그램 내용

...
for (int i = 1; i < n; i++)
{
	if( x_i == 0 )	/// update all possible numbers 
	{
		for (int j = 1; j <= m; j++)
		{
			k = min(1, j);
			dp[i][k] += (dp[i-1][k-1] + dp[i-1][k] + dp[i-1][k+1]) % MOD;
		}
	}
	else	/// update x_i
	{
		dp[i][x_i] += (dp[i-1][x_i-1] + dp[i-1][x_i] + dp[i-1][x_i+1]) % MOD;
	}
}
...      

 

Dynamic Programming ( link )