[Baekjoon Online Judge] 백준 1890번 점프(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1890번 점프

(C++, Python)

(글쓴날 : 2020.04.20)

 

---

* Baekjoon Online Judge, 백준 1890번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1890번 점프

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1890

1890번: 점프

---

2) 풀이 과정

* 시간 복잡도 : O(n³)

 

오른쪽 혹은 아래쪽으로 점프할 수 있는 숫자들이 적혀있는 N X N 크기의 게임판이 주어지고,

가장 왼쪽 위 칸을 출발 지점, 가장 오른쪽 아래 칸을 도착 지점이라 할 때, 이동 가능한 경로의 개수를 구하는 문제입니다.

 

저의 경우, 동적 계획법을 적용하였으며, C++과 Python을 사용했습니다.

먼저, memoization할 2차원 테이블을 만든 뒤, 게임판을 완전 탐색하면서 탐색 중인 인덱스를 기준으로 왼쪽과 위쪽을 한 번 더 탐색해 해당 인덱스로 올 수 있는 경로의 개수를 기록하여 문제를 해결했습니다.

단, 경로의 개수가 int형의 범위를 벗어날 수 있으므로, C++의 경우 memoization할 타입을 long long으로 지정해 주셔야 합니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
 
using namespace std;
 
int gameboard[101][101];
long long memoization[101][101];
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int N = 0;
    cin >> N;
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> gameboard[i][j];
 
    int ii = 0;
    int jj = 0;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            ii = i;
            jj = j;
 
            for (int x = 0; x < ii; x++)
            {
                if (gameboard[x][j] == i - x)
                {
                    if (!x && !j)
                    {
                        memoization[i][j] = 1;
                        break;
                    }
                    if (memoization[x][j])
                        memoization[i][j] += memoization[x][j];
                }
            }
 
            for (int y = 0; y < jj; y++)
            {
                if (gameboard[i][y] == j - y)
                {
                    if (!y && !i)
                    {
                        memoization[i][j] = 1;
                        break;
                    }
                    if (memoization[i][y])
                        memoization[i][j] += memoization[i][y];
                }
            }
        }
    }
 
    cout << memoization[N - 1][N - 1];
 
    return 0;
}

---

* Python 코드

import sys
input = sys.stdin.readline
 
N = int(input())
gameBoard = [list(map(int , input().split())) for _ in range(N)]
memoization = [[0] * N for _ in range(N)]
 
for i in range(N):
    for j in range(N):
        ii = i
        jj = j
        
        for x in range(ii):
            if gameBoard[x][j] == i - x:
                if not x and not j:
                    memoization[i][j] = 1
                    break
                if memoization[x][j]:
                    memoization[i][j] += memoization[x][j]
 
        for y in range(jj):
            if gameBoard[i][y] == j - y:
                if not y and not i:
                    memoization[i][j] = 1
                    break
                if memoization[i][y]:
                    memoization[i][j] += memoization[i][y]
 
print(memoization[-1][-1])

---