백준 3372. 보드 점프

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

3372번: 보드 점프

 

dp 문제긴 한데, 다이나믹 프로그래밍보다는 BigInteger 에 대한 내용이었다.

문제의 로직은 그냥 단순한 dp 문제다.

 

d[i][j] : [i][j]에 도달가능한 경로의 수 로 두고, 

[i][j]에서 이동 가능한 두 좌표에 d[i][j] 값을 더해 주면 된다.

 

그런데 문제를 보면 경로의 수는 2^63-1 보다 클수 있으며, 100 자리가 넘는다고 나와있다.

즉 일반적인 자료형으로는 풀수 없다.

 

검색을 해보니 파이썬은 BigInteger 클래스가 기본 제공되고, 자바도 기본 라이브러리에 있는 것 같다.

하지만 c++은 기본적으로는 없어서 구글링해서 찾아왔다.

 

https://github.com/faheel/BigInt

GitHub - faheel/BigInt: Arbitrary-sized integer class for C++