[백준/C++] 24392 영재와 징검다리

https://www.acmicpc.net/problem/24392

 

코드

#include <iostream>
using namespace std;

#define MAX 1001
#define MOD 1000000007
#define FASTIO ios::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;
int arr[MAX][MAX], n, m, dp[MAX][MAX];
ll ans;

int main() {
	FASTIO;
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (i == 0) dp[i][j] = arr[i][j];
		}
	}

	for (int i = 1; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 1) {
				dp[i][j] = dp[i - 1][j]; 
				if (j > 0 && arr[i - 1][j - 1] == 1)
					dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD;
				if (j < m - 1 && arr[i - 1][j + 1] == 1) 
					dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MOD;
			}
		}
	}


	for (int i = 0; i < m; i++) {
		ans = (ans + (dp[n - 1][i] % MOD)) % MOD;
	}
	cout << ans;
	return 0;
}

 

설명

arr[i][j]가 1일 때 이전 단계에서 arr[i][j]로 올 수 있는 경우의 수를 dp 배열에 누적해서 계산하면 됩니다. 이때 j의 인덱스 구간 확인 후 더하기가 발생할 때마다 나머지 연산도 같이 해주면서 진행합니다. 최종적으로 dp 배열의 마지막 행에서 최댓값을 찾아 출력합니다.

 

느낀 점

비슷한 유형의 문제를 많이 풀고 있는데, 한 번에 식을 세워서 풀었습니다!