tose33

https://www.acmicpc.net/problem/1793 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 n이 주어진다. www.acmicpc.net 이 문제는 dp 문제긴한데 cpp로 풀었을시 dp보다는 big integer 문제에 가깝다. 파이썬 같은 언어는 big integer에 대한 고민 없이 dp에 대한 고민만 하면 된다. 하지만 cpp는 숫자를 string으로 저장하고 계산할때만 int로 계산하고 다시 string으로 저장하는 형태로 풀어야 한다. 가로 (2x1) 타일, 세로 (2x1) 타일, (2x2) 타일을 기존 타일에 이어 붙여나가면 된다. 세로 (2x1) 타일은 세로로 1칸 증가할수 있기 때문에 i-1 경..

https://www.acmicpc.net/problem/3372 3372번: 보드 점프 N × N 게임 보드에 양의 숫자들이 적혀있다. 목적은 왼쪽 위에서 오른쪽 아래까지 규칙에 맞게 점프를 해서 가는 것이다. 숫자들은 현재 점에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 www.acmicpc.net dp 문제긴 한데, 다이나믹 프로그래밍보다는 BigInteger 에 대한 내용이었다. 문제의 로직은 그냥 단순한 dp 문제다. d[i][j] : [i][j]에 도달가능한 경로의 수 로 두고, [i][j]에서 이동 가능한 두 좌표에 d[i][j] 값을 더해 주면 된다. 그런데 문제를 보면 경로의 수는 2^63-1 보다 클수 있으며, 100 자리가 넘는다고 나와있다. 즉 일반적인 자료형으로는 풀수 없다..