1890

도착 할 경로가 몇개나 있는지 묻는 문제이다.

도착 할 좌표의 경로를 찾는데 집중 하기 보다는

각 좌표까지 이동 할 수 있는 경우의 수들을 모두 계산 한 후

마지막에 도착 지점의 경우의 수를 구해주면 풀기 쉽다.

#include<iostream> #include<cstdio> #include<fstream> using namespace std; int main() { int n; int map[100][100]; unsigned long long d[100][100]; ifstream ifp("input.txt"); scanf("%d", &n); for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){ //scanf("%d", &map[i][j]); ifp>>map[i][j]; d[i][j] = 0; } d[0][0] = 1; for(int i=0; i < n; i++) for(int j=0; j<n; j++){ if(d[i][j] > 0 && map[i][j]!=0){ if(i + map[i][j] < n){ d[i+map[i][j]][j] += d[i][j]; } if(j + map[i][j] < n){ d[i][j+map[i][j]] += d[i][j]; } } } printf("%llu\n", d[n-1][n-1]); return 0; }

여기서 도착할 경로의 범위가 2^63 까지 된다고 했는데

unsinged long long을 위 범위를 표현할 수 있다

printf로 표현하는 방법은 "%llu%이다.

방학도 끝났으니 분발해야겠다.