[백준 1890번] 점프 (C++)

문제링크 : https://www.acmicpc.net/problem/1890

#include <bits/stdc++.h> 
using namespace std;


int arr[100][100];
long long dp[100][100];  //범위가 크므로 long long 선언
int n;

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> arr[i][j];  //게임판 입력
		}
	}

	dp[0][0] = 1; //무조건 첫번째 값은 지나므로 초기화 값은 1

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (arr[i][j] == 0) { break; }  //마지막 값(0)일 경우 멈춤, 안 멈추면 아래 계산을 진행하여 틀린 답이 저장됨
			if (i + arr[i][j] < n) { dp[i + arr[i][j]][j] += dp[i][j]; };  //좌측 이동 점화식
			if (j + arr[i][j] < n) { dp[i][j + arr[i][j]] += dp[i][j]; };  //하단 이동 점화식
		}
	}

	cout << dp[n - 1][n - 1];
}

arr[i][j] == 0 일때 멈추지 않는다면,

조건 만족으로 인해 아래 점화식에 대한 계산을 진행하여 틀린 답을 저장하므로 올바르게 멈춰주어야 한다.