[C++] 백준/BOJ - 1890 : 점프

---

문제 이해 단계

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

각 칸마다 이동해야 하는 칸 수가 적혀 있고,
가장 왼쪽 위 칸에서 오른쪽 아래 칸으로 이동해야 한다.

즉, 해당 칸에 도착했을 때 0이면 움직임이 멈춘다.(더 이상 이동하지 못하기 때문)

할 수 있는 움직임은 아래로 이동하거나 왼쪽으로 이동하거나 2가지이다.

이러한 조건일 때 가장 오른쪽 아래로 이동할 수 있는 경우의 수를 구하는 문제.

 

 

---

문제 접근 단계

가장 오른쪽 아래로 이동할 수 있는 경우의 수를 구하는 것이기 때문에
오른쪽 아래에서부터 역으로 출발하는 걸로 생각했다.

게임판의 크기가 NxN일 때, 마지막 칸으로 움직일 수 있는 경우는 무엇이 있을까?

그림으로 생각해 보면 이런 식이 될 것이다.

이런 식으로 마지막칸에 도착할 수 있는 경우는
좌측에서 오는 (1~N-1), 위에서 오는 (1~N-1)이다.

그렇다면 이 많은 경우를 하나하나 살펴봐야 할까? 그렇지 않다.

좌측 1(그림에서 0 바로 옆에 있는 곳)에서 오는 걸로 생각해 보자.

만약 해당 칸에 적혀있는 숫자가 1이 아닌 다른 숫자면 어떻게 될까?
0인 칸으로 갈 수 없을 것이다.

따라서
해당 칸에서 역으로 이동되어 추적되는 칸과 
안에 적혀있는 값이 일치해야 이동가능한 칸이다.

이는 0인 칸뿐만 아니라, 다른 칸에도 적용되는 규칙일 것이다.

그렇기 때문에 이를 재귀함수로 구현하여 함수를 반복하다가,
최종적으로 가장 왼쪽 위에 칸에 도달하면 이동가능한 경우의 수라고 할 수 있다.

모든 칸에 대해 해당 재귀함수를 돌리면 엄청난 시간적인 부담이 들것이기 때문에
메모라이즈 기법 즉, DP를 사용하여 계산결과를 저장하면서
이미 계산된 결과를 이용하면서 값을 구하기로 한다.

2차원 저장공간 d를 두어 해당 좌표일 때의 이동가능 경우의 수를 저장해 두어 중복된 연산을 막는다.

그런데 한 가지 문제가 생긴 것은 문제 조건에서 출력은 2^63-1 이하의 답이 나온다고 했다.

이건 무조건 long long을 초과하는 답이 나오기 때문에 큰 수의 합을 하는 연산을 해야 한다.

즉 값들을 문자열로 바꾸고, 문자열끼리 더하여 오버플로우가 발생하지 않도록 해야 한다.

자세한 것은 코드에서 설명하겠다.

 

 

---

문제 구현 단계

bool CheckMove(int x,int num){
    if(x == num) return true;
    else return false;
}
string AddNum(string num1, string num2){
    int size = max(num1.size(),num2.size());
    int sum = 0;
    string num = "";
    for(int i = 0; i < size || sum; i++){
        if(num1.size() > i) sum += num1[i] - '0';
        if(num2.size() > i) sum += num2[i] - '0';
        num += sum%10 + '0';
        sum /= 10;
    }
    return num;
}

일단 Dp함수를 보기 전,
해당 칸에서 오는 이동이 유효한 것인지 체크하는 CheckMove와
두 수를 문자열로 더하는 AddNum 함수에 대해서 살펴보도록 하겠다.

CheckMove는 매개변수로 칸에 적힌 이동값과 이동값을 받는다.
이때, 이 두 값이 일치하면 true, 그렇지 않으면 false를 반환한다.

AddNum은 stirng을 반환하고 문자열 num1과 num2를 매개변수로 받는다.

두 문자열 중 길이가 더 긴 것을 size로 잡고,
자릿수끼리 문자열을 숫자로 전환하여 더한 후 다시 문자열로 전환한다.

이 과정을 계속 반복한 후 그 값을 문자열로 쌓아뒀던 num을 반환한다.

이 과정에 대해서는 이전에 풀어놨던 문제에 자세히 설명돼 있으니 참고하길 바란다.

https://howudong.tistory.com/45?category=1255705 

이제 Dp함수를 위한 사전 준비가 끝났으니 Dp함수에 대해서 설명하겠다.

int map[101][101];
string d[101][101];

string Dp(int x, int y){
    if(!(x == N && y == N) && map[x][y] == 0) return "0";
    if(x <= 0 || y <= 0)return "0";
    if(x == 1 && y == 1) return "1";
    if(d[x][y] != "") return d[x][y];

    string a ="0";
    string b ="0";
    for(int i = 1; i< N; i++){
        if(CheckMove(map[x-i][y],i)){
            a = AddNum(a,Dp(x-i,y));
        }
        if(CheckMove(map[x][y-i],i)){
            b = AddNum(b,Dp(x,y-i));
        }
    }
return d[x][y] = AddNum(a,b);
}

핵심이 되는 Dp함수이다.

매개변수로 게임판에서의 위치를 x와 y좌표로 나타낸 x, y를 매개변수로 받는다.
그리고 게임판의 상태를 입력받을 map을 2차원으로 저장하였다.

Dp를 위한 2차원배열 d는 문자열로 저장하기 위해 stirng으로 저장하였다.

Dp함수를 자세히 살펴보자.

우선 NxN의 범위를 벗어나면 실패한 것으로 간주함으로 0을 저장한다.
그리고 가장 처음 칸(x= 1 && y = 1)에 도달하면 1을 저장한다.

이미 d [x][y]에 계산된 값이 있으면 그 값을 반환하여
중복된 연산을 막아 쓸데없는 시간소모를 줄인다.

이제 중요한 계산으로 넘어가 보자.

변수 a에는 오른쪽으로 이동할 때의 유효한 경우의 수를 저장한다.
변수 b에는 아래로 이동할 때의 유효한 경우의 수를 저장해 둔다.

CheckMove로 해당 칸으로의 이동이 유효할 때의 경우의 수를
AddNum으로 문자열로 변환하여 더한다.

이 작업을 재귀함수로 반복하여 2차원함수 d에 저장하는 것을 반복하는 것으로 Dp를 구성하였다.

이제 전체 코드를 올리고 설명을 끝내겠다.

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int N;
int map[101][101];
string d[101][101];

bool CheckMove(int x,int num){
    if(x == num) return true;
    else return false;
}
string AddNum(string num1, string num2){
    int size = max(num1.size(),num2.size());
    int sum = 0;
    string num = "";
    for(int i = 0; i < size || sum; i++){
        if(num1.size() > i) sum += num1[i] - '0';
        if(num2.size() > i) sum += num2[i] - '0';
        num += sum%10 + '0';
        sum /= 10;
    }
    return num;
}
string Dp(int x, int y){
    if(!(x == N && y == N) && map[x][y] == 0) return "0";
    if(x <= 0 || y <= 0)return "0";
    if(x == 1 && y == 1) return "1";
    if(d[x][y] != "") return d[x][y];

    string a ="0";
    string b ="0";
    for(int i = 1; i< N; i++){
        if(CheckMove(map[x-i][y],i)){
            a = AddNum(a,Dp(x-i,y));
        }
        if(CheckMove(map[x][y-i],i)){
            b = AddNum(b,Dp(x,y-i));
        }
    }
return d[x][y] = AddNum(a,b);
}
int main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);

    cin >> N;

    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++) cin >> map[i][j];
    }
    string ans = Dp(N,N);
    reverse(ans.begin(),ans.end());
    cout << ans;
}

 

 

---

시행착오

이 문제는 나름대로 이전에 풀어왔던 문제들 덕분에 오래 걸리지는 않았다.

또한 큰 수의 덧셈은 위에 링크에서 보았듯 한번 고생해 봤기 때문에 손쉽게 구현할 수 있었다.

DP구현 원리는 의외로 생각하기 쉬웠어서 그리 어려웠던 문제는 아니었던 것 같다.

큰 수의 덧셈 + DP구현 섞어서 낸 문제여서 실버 1이었던 문제 같다.