백준 1890 점프 with Python

알고리즘

다이나믹 프로그래밍

Tip

다이나믹 프로그래밍(Dynamic Programming, DP)은 반복되는 부분 문제를 해결하기 위해 이전에 계산된 결과를 저장하고 재사용하는 알고리즘입니다. DP 문제는 다음과 같은 두 가지 특성을 가지고 있습니다.

Overlapping Subproblems: 하나의 큰 문제를 여러 개의 작은 문제로 나눌 수 있고, 작은 문제들이 서로 중복될 수 있습니다.
Optimal Substructure: 큰 문제의 최적 해는 작은 문제들의 최적 해로 구성됩니다.

DP 문제를 해결하기 위해서는 다음과 같은 단계를 거칩니다.

문제를 작은 부분 문제로 나눕니다. 부분 문제들의 최적 해를 계산합니다. 부분 문제들의 최적 해를 사용하여 전체 문제의 최적 해를 계산합니다. DP 문제를 해결하는 데는 크게 두 가지 방법이 있습니다.

Memoization : 재귀호출을 사용한 하향식 방법입니다. 메모이제이션 방식은 부분 문제의 최적 해를 저장하는 테이블을 사용합니다. 재귀호출을 사용하여 부분 문제를 해결할 때마다 테이블을 참조하여 이미 계산된 부분 문제의 최적 해를 사용합니다.
Tabulation : 상향식 방법입니다. 부분 문제의 최적 해를 계산하여 표로 표현하는 방법입니다. 부분 문제의 최적 해는 작은 부분 문제에서부터 큰 부분 문제로 순서대로 계산됩니다.

DP 문제를 해결하는 데는 다음과 같은 팁이 있습니다.

문제를 잘 분해하는 것이 중요합니다. 부분 문제가 잘 분해되면 전체 문제의 최적 해를 구하기가 쉬워집니다.
부분 문제의 최적 해를 계산하는 방법을 찾는 것이 중요합니다. 부분 문제의 최적 해를 계산할 수 없으면 DP를 적용할 수 없습니다.
memoization이나 tabulation을 적절하게 사용하는 것이 중요합니다. memoization이나 tabulation을 사용하면 DP 문제를 효율적으로 해결할 수 있습니다.

풀이 과정

처음에는 재귀호출을 활용한 dfs + memoization 방식(하향식)으로 풀었는데 메모리 초과로 실패했다. (4 ≤ N ≤ 100)의 경우의 수가 생각보다 많아서 함수 호출 횟수가 많아졌다.

따라서 이 문제는 상향식으로 해결하는 것이 좋다.

풀이 방법은 다음과 같다.

먼저 다이나믹 프로그래밍을 푸는 방법을 적용한다. 큰 문제를 보다 작은 문제들로 분해한다. 위의 그림에서 종착점인 0으로 이동하는 경우의 수는 그림 2처럼 3가지다.
그리고 종착점 바로 전 단계인 인덱스는 4행 2열(1), 3행 4열(1), 4행 1열(3) 3개다.

마지막 종착점까지 도달하는 경우의 수가 s(-1)이고 바로 전 단계까지 도달하는 경우의 수를 s(-2)라고 한다면, s(-1)은 s(-2) 각각을 모두 합한 결과라고 할 수 있다. (위의 예시에서 0까지 도달하는 경우의 수는 4행 2열(1), 3행 4열(1), 4행 1열(3) 3곳으로 도달하는 경우의 수 각각을 합한 것이다)
Tabulation 방법을 적용하기 위해 새로운 배열을 생성하고 모두 0으로 초기화한다. 각각의 인덱스는, 시작점부터 해당 인덱스까지 도달하는 경우의 수가 된다.
시작점을 1로 설정한다.
이중 for문을 돌린다. 각 인덱스에서 이동할 수 있는 인덱스에, 현재 인덱스만큼을 더해준다.
반복문이 끝나면 종착점 인덱스에 정답이 적혀있게 된다.

전체 코드

import sys


input = sys.stdin.readline

N = int(input())
board = [list(map(int, input().strip().split())) for _ in range(N)]

dp = [[0] * N for _ in range(N)]
dp[0][0] = 1  # 초기 값

# 반복문을 통해 갈 수 있는 그래프의 좌표를 탐색
for i in range(N):
    for j in range(N):
        # 현재 탐색하는 좌표가 오른쪽 맨 끝 점이면 반복을 멈춘다.
        if i == N - 1 and j == N - 1:
            print(dp[i][j])
            break

        # 오른쪽으로 이동
        if j + board[i][j] < N:
            dp[i][j + board[i][j]] += dp[i][j]

        # 아래로 이동
        if i + board[i][j] < N:
            dp[i + board[i][j]][j] += dp[i][j]

마지막에 dp를 찍어보면 다음과 같이 나온다.

[1, 0, 1, 0]
[0, 0, 0, 0]
[1, 1, 0, 1]
[1, 0, 1, 3]

알고리즘 문제 풀이

백준 1890 점프 with Python

알고리즘

Tip

풀이 과정

전체 코드