백준 1890 c++ "점프" -PlusUltraCode-

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

 

[필자 사고]

동적프로그래밍 문제이다.

필자는 보통 이런 문제는 최대값을 구한는 문제 형태로 나온다.

그래서 처음 필자가 생각한 풀이는 현재 지점에서 이전에 올 수 있는 경로들에서 최대값을 가져와서 반영한다"와 같은 식으로 점화식을 설계해 왔다.

 

그러나 이 문제는 현재 지점에서 다음으로 갈 위치에 값을 누적해서 더해주는 형태로 짜줘야 됐다. 

사고의 전환이 일어나서 좋은 문제였던거 같다.

[코드 해설]

2. 입력 처리 (Input 함수)

Input() 함수는 다음과 같은 역할을 한다.

1. 입력 처리
   • cin >> N;을 통해 N 값을 입력받는다.
   • arr 벡터와 dp 벡터를 크기 (N+1) x (N+1)로 동적 할당한다.
2. 격자 정보 입력
   • arr[i][k] 값은 각 칸에서 이동할 수 있는 거리를 나타낸다.
3. 시작 위치 설정
   • dp[1][1] = 1; (출발점에서의 경로 수는 1)

---

3. 유효한 위치 검사 (isInside 함수)

isInside(sero, garo) 함수는 주어진 좌표가 격자 내부에 있는지 확인한다.

• (1 ≤ sero, garo ≤ N) 범위 안에 있으면 true 반환, 아니면 false 반환.

---

4. 동적 프로그래밍을 이용한 이동 경로 계산 (Game_Start 함수)

Game_Start() 함수는 동적 프로그래밍을 이용하여 가능한 경로의 개수를 계산한다.

(1) 이동 과정

• (i, k) 위치에서 이동할 수 있는 값 arr[i][k]을 확인하여 두 방향(오른쪽, 아래)으로 이동을 시도한다.
• dp[nowSero][nowGaro] 값이 dp[nextSero][nextGaro]에 더해진다.

(2) 오른쪽 이동

• nextGaro = nowGaro + arr[i][k]
• nextSero = nowSero
• 유효한 위치인지 확인 후 dp[nextSero][nextGaro] += dp[nowSero][nowGaro];

(3) 아래쪽 이동

• nextSero = nowSero + arr[i][k]
• nextGaro = nowGaro
• 유효한 위치인지 확인 후 dp[nextSero][nextGaro] += dp[nowSero][nowGaro];

[소스 코드]

	#include <iostream>
	#include <vector>
	#include <cmath>
	#define ll long long
	using namespace std;

	ll N;
	vector<vector<ll>> arr;
	vector<vector<ll>> dp;

	void Input() {
		cin >> N;
		arr.resize(N + 1);
		dp.resize(N + 1);
		for (int i = 0; i <= N; i++) {
			arr[i].resize(N + 1);
			dp[i].resize(N + 1);
		}

		for (int i = 1; i <= N; i++) {
			for (int k = 1; k <= N; k++) {
				cin >> arr[i][k];
			}
		}
		dp[1][1] = 1;
	}
	bool isInside(int sero, int garo) {
		if (sero >= 1 && sero <= N && garo >= 1 && garo <= N)return true;
		return false;
	}


	void Game_Start() {
		int nowSero = 1;
		int nowGaro = 1;
		for (int i = 1; i <= N; i++) {

			for (int k = 1; k <= N; k++) {
				nowSero = i;
				nowGaro = k;
				if (nowSero == N && nowGaro == N) {
					cout << dp[N][N];
					return;
				}
				//가로로 이동하는 경우
				int nextGaro = nowGaro + arr[i][k];
				int nextSero = nowSero;
				if (isInside(nextSero, nextGaro) == true) {
					dp[nextSero][nextGaro] += dp[nowSero][nowGaro];
				}
			
				//아레로 이동하는경우
				 nextGaro = nowGaro;
				 nextSero = nowSero + +arr[i][k];
				if (isInside(nextSero, nextGaro) == true) {
					dp[nextSero][nextGaro] += dp[nowSero][nowGaro];
				}
			}
		}

	
	}

	int main(void) {
		Input();
		Game_Start();
	}