[BaekJoon] 백준 11909번 배열 탈출

[BaekJoon] 백준 11909번 배열 탈출

 

🎈문제

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

💬설명

• dp로 푸는 문제
• 가장 마지막 점인 n,n위치까지 가는 최소 비용의 경로는 이전 경로들의 최소값에 기반하여 나온다. 따라서 이전 값들을 저장해두면서 계산한다.
• 처음에는 다익스트라 문제라고 생각해서 풀었는데 시간초과가 났다.. 다익스트라로도 풀수 있을 것 같긴한데 시간 고민해봐야 할 것 같다.

👩‍💻코드

# BaekJoon19236.py
import sys
input = sys.stdin.readline


n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
    for j in range(n):
        # 초기 값인 경우
        if i == 0 and j == 0:
            continue
        elif i == 0:
            cost1 = dp[i][j - 1] if board[i][j] < board[i][j - 1] else dp[i][j - 1] + board[i][j] - board[i][j - 1] + 1
            dp[i][j] += cost1
        elif j == 0:
            cost2 = dp[i - 1][j] if board[i][j] < board[i - 1][j] else dp[i - 1][j] + board[i][j] - board[i - 1][j] + 1
            dp[i][j] += cost2
        else:
            cost1 = dp[i][j - 1] if board[i][j] < board[i][j - 1] else dp[i][j - 1] + board[i][j] - board[i][j - 1] + 1
            cost2 = dp[i - 1][j] if board[i][j] < board[i - 1][j] else dp[i - 1][j] + board[i][j] - board[i - 1][j] + 1
            dp[i][j] = min(cost1, cost2)

print(dp[n - 1][n - 1])

 

👉참고

https://github.com/HyeonJinGitHub/LearningRepository/blob/master/%EB%B0%B1%EC%A4%80/11909%20%EB%B0%B0%EC%97%B4%20%ED%83%88%EC%B6%9C/%EC%95%88%ED%98%84%EC%A7%84(21.04.05).py