백준 1890번 점프

🔒[문제 url]

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

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
#include <set>
//#include <map>
using namespace std;

int n;
int map[100][100];
unsigned long long dp[100][100]; // dp[x][y] : x행 y열로 갈 수 있는 경로의 개수

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];
}


void SOLVE()
{
	dp[0][0] = 1;


	/*Bottom Up Dynamic Programming
	* 
	* 오른쪽과 아래로만 이동할 수 있기때문에,
	* (한 지점이 속한 행과 열)의 (이전 지점)으로 갈 수 있는 경로가 있다면,
	* 해당 지점의 dp에 모든 경로의 수를 더하여 갱신해준다.
	* 
	* 이때, 이전 지점으로 갈 수 있다고 무작정 더하는 것이 아니라,
	* 이전 지점의 값을 확인해 현재 지점으로 올 수 있는지또한 확인한다.
	* 
	* 즉,
	* 이전 지점의 dp값이 0 이 아니면서,
	* 이전 지점의 위치 + 이전 지점의 값(점프 거리)을 했을 때 현재 지점이 나온다면,
	* dp를 갱신해준다.
	* 
	*/
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			// 초기화 예외 처리 안 해주면 전부 다 0으로 갱신됨!
			if (i == 0 && j == 0) continue;

			unsigned long long routeCnt = 0; // type 주의
			// 해당 지점 행
			for (int k = 0; k < j; k++)
				// 이전 지점으로의 경로가 존재하고, 이전 지점에서 현재 지점으로 올 수 있으면
				if (dp[i][k] && k + map[i][k] == j) routeCnt += dp[i][k];

			// 해당 지점 열
			for (int k = 0; k < i; k++)
				// 이전 지점으로의 경로가 존재하고, 이전 지점에서 현재 지점으로 올 수 있으면
				if (dp[k][j] && k + map[k][j] == i) routeCnt += dp[k][j];

			// dp 갱신
			dp[i][j] = routeCnt;
		}

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

int main()
{
	INPUT();

	SOLVE();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.