백준 3372 보드 점프

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

3372번: 보드 점프

마지막에만 0 들어오는 줄 알고 예외처리 안 했더니 메모리 초과가 뜹니다.

 

N*N 맵에 입력으로 주어지는 숫자만큼 오른쪽 혹은 아래로 이동가능할 때 왼쪽 위에서 오른쪽 아래로 이동가능한 경로의 수를 구하는 문제입니다. 

 

dp 문제로 쉽게 접근할 수 있지만 주의할 점은 총 경우의 수가 2^63보다 클 수 있기에 long long으로도 커버가 안 되므로 string으로 덧셈을 구현해서 풀었습니다.

 

dp 접근은 마지막 칸까지 갈 수 있으면 경우의 수가 1개있는 것이고 칸을 벗어나거나 0인 칸이면 (마지막 제외) 갈 수 있는 경로는 0개입니다.

그리고 dp[y][x]가 빈 칸이 아닌 경우, 해당 지점에서 갈 수 있는 경로는 알고 있는 것이므로 해당 dp값을 리턴시키면 됩니다.

 

코드는 다음과 같습니다.

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;

int n;
int map[101][101];
string dp[101][101];

void init()
{
    cin >> n;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> map[i][j];
            dp[i][j] = "";
        }
    }
}

string bigSum(string s1, string s2) 
{
    int size = max(s1.size(), s2.size()) + 1;
    string result(size, '0');
    
    if(s1.size() > s2.size()) {
        int diff = s1.size() - s2.size();
        string tmp(diff, '0');
        tmp += s2;
        s2 = tmp;
    }
    else if(s1.size() < s2.size()) {
        int diff = s2.size() - s1.size();
        string tmp(diff, '0');
        tmp += s1;
        s1 = tmp;
    }
    
    int carry = 0;
    for(int i = s1.size() - 1; i >= 0; i--) {
        int sum = (s1[i] - '0') + (s2[i] - '0') + carry;
        carry = sum / 10;
        sum %= 10;
        result[i + 1] = sum + '0';
    }
    result[0] = carry + '0';
    
    if(result[0] == '0')
        return result.substr(1);
    else 
        return result;
}

string calc(int y, int x)
{
    if(y == (n - 1) && x == (n - 1))
        return "1";
    if(y >= n || x >= n || y < 0 || x < 0)
        return "0";
    if(map[y][x] == 0)
        return "0";
    if(dp[y][x] != "")
        return dp[y][x];
    
    int ny = y + map[y][x];
    int nx = x + map[y][x];
    
    dp[y][x] = bigSum(calc(ny, x), calc(y, nx));
    return dp[y][x];
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    init();
    
    calc(0, 0);
    cout << dp[0][0];
}