보드 점프 (feat. 백준, 3372번)

보드 점프
https://www.acmicpc.net/problem/3372

3372번: 보드 점프

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
void add_string(string in1, string in2, string& out) {
	out.clear();
	int big_size = max(in1.size(), in2.size());
	while (big_size != in1.size())
		in1 = "0" + in1;
	while (big_size != in2.size())
		in2 = "0" + in2;
	int data = 0;
	for (register int i = big_size - 1, v; i >= 0; --i) {
		v = (in1.at(i) - '0') + (in2.at(i) - '0') + data;
		if (v > 9)
			data = 1, v -= 10;
		else
			data = 0;
		out = to_string(v) + out;
	}
	if (data == 1)
		out = to_string(data) + out;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N;
	int arr[101][101];
	string dp[101][101];
	cin >> N;
	for (register int i = 1, j; i <= N; ++i)
		for (j = 1; j <= N; ++j)
			cin >> arr[i][j], dp[i][j] = "0";
	dp[1][1] = "1";
	for (register int x = 1, y; x <= N; ++x)
		for (y = 1; y <= N; ++y) {
			if ((x == N && y == N) || (dp[x][y] == "0"))
				continue;
			register int dist = arr[x][y];
			register int down = x + dist;
			register int right = y + dist;
			if (down <= N)
				add_string(dp[x][y], dp[down][y], dp[down][y]);
			if (right <= N)
				add_string(dp[x][y], dp[x][right], dp[x][right]);
		}
	cout << dp[N][N] << "\n";
	return 0;
}
// *&)*@*

 

해당 문제는 아래 "점프" 와 유형은 동일하나 경로의 개수가 long long 자료형 이상일 수 있다는 조건이 있습니다.

점프 (feat. 백준, 1890번)

 

1. 경로를 long long 자료형이 아닌 string 자료형으로 변경하였습니다.
2. string과 string을 더하는 add_string 함수를 구현하였습니다. (string간 동일한 인덱스간 값을 더하고 만약 10보다 크다면 다음 인덱스 연산에 1을 보상하는 방식입니다.)