[C++] 백준 1890번 점프

다이나믹 프로그래밍 문제.

처음에 Bottom-Up 방식으로 시도했는데 틀렸다.

Top-Down 방식으로 풀었을 때에도 방문처리를 안했어서 틀렸다.

[C++] 백준 1520번 내리막 길

위 문제와 거의 유사한 문제이다.

난이도는 왜이렇게 차이나는지는 모르겠지만, 위 문제를 풀 수 있다면 이 문제도 풀 수 있다.

 

문제풀이

다이나믹 프로그래밍의 TOP DOWN 방식과 DFS과 비슷한 로직을 혼용해서 풀었다.

(1, 1)에서 시작해서 오른쪽, 아래쪽 방향으로 가면서

(r, c) 칸에서 (N, N)칸 까지 가는 경로의 수를 저장하는 방식으로 풀었다.

사실 위에 내리막 길 문제의 풀이와 거의 유사하다.

 

4 2 3 3 1 1 2 1 3 1 2 3 1 3 1 1 0

위 예시 입력의 경우, 다음과 같은 순서로 진행된다.

처음에 (1, 1)에서 시작된다.

1. (1, 1) : (1, 3) -> (4, 4)까지 경로의 수 + (3, 1) -> (4, 4)까지 경로의 수
2. (1, 3) : (1, 6)에서는 6 > 4 이므로 불가능. / (4, 3) -> (4, 4)까지 경로의 수
3. (4, 3) : (4, 4) -> (4, 4)까지 경로의 수 + (5, 3) 5 > 4이므로 불가능.
4. (4, 4) : (N, N)은 1가지 방법 뿐.
5. ...

이런 식으로 TOP DOWN 방식으로 위에서부터 아래를 채워나가는 식으로 풀면 된다.

코드를 살펴보자.

 

/*
* 백준 1890번 점프
* https://www.acmicpc.net/problem/1890
* 다이나믹 프로그래밍
*/
#include <iostream>
using namespace std;

int widthHeight;
int board[101][101];
long long dp[101][101];
bool visit[101][101];

long long go(int r, int c) {
	if (r == widthHeight && c == widthHeight) { return 1; }
	if (visit[r][c]) { return dp[r][c]; }

	visit[r][c] = true;

	pair<int, int> toRight = { r, c + board[r][c] };
	pair<int, int> toBottom = { r + board[r][c], c};

	if (toRight.second <= widthHeight) {
		dp[r][c] += go(r, toRight.second);
	}

	if (toBottom.first <= widthHeight) {
		dp[r][c] += go(toBottom.first, c);
	}

	return dp[r][c];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> widthHeight;

	for (int i = 1; i <= widthHeight; i++) {
		for (int j = 1; j <= widthHeight; j++) {
			cin >> board[i][j];
		}
	}

	go(1, 1);

	cout << dp[1][1];

	return 0;
}

코드가 길지 않으므로 코드 전문으로 살펴보자.

 

특별히 어려운 것은 없다.

 

변수에 대한 설명은 다음과 같다.

• widthHeight : 입력받는 크기 N
• board 배열 : 각 칸이 오른쪽, 아래쪽으로 몇 칸 움직일 수 있는지 저장하는 배열
• dp 배열 : 각 칸(r, c)에서 (N, N)까지 몇 개의 경로가 있는지 저장하는 배열
• visit 배열 : 각 칸을 방문했는지 여부를 조사하는 배열. 한 칸을 방문했다는 뜻은 해당 칸에서 (N, N)까지 경로를 구했다는 것을 의미하므로 다시 탐색할 필요가 없다.

 

메인함수에서는 크기 N을 입력받고 각 칸에 대한 정보를 입력받는다.

그리고 TOP DOWN 메서드인 go 메서드를 호출한다. 우리는 (1, 1)에서 (N, N)까지 거리가 궁금하므로

go(1, 1)을 호출한다. 

 

TOP DOWN 메서드는 다음과 같다.

• 만일 (N, N)이라면 1을 return한다.
• 만일 현재 칸을 방문했었다면 이미 해당 칸에서 (N, N)까지 경로를 구한 상황이다 dp[r][c]를 return한다.
• 아니라면 현재 칸을 방문처리 해주고 현재 칸에서 갈 수 있는 오른쪽, 아래쪽의 좌표를 구해서 유효한 좌표라면 해당 칸에서 다시 한번 (N, N)까지 갈 수 있는 경로를 dp[r][c]에 더해준다.
• dp[r][c]를 return한다.

 

처음에 Bottom-Up 방식으로 풀었다가 계속 틀렸었다.

그러다가 예전에 푼 내리막길 문제의 방식으로 풀었는데 시간 초과가 났다.

이는 방문처리를 안해서 틀린거였다.

 

GitHub - kimyunseok/cpp: my study-record

코드 전문은 위에서 확인 가능하다.