[백준11909/골드5] 배열 탈출 - Python

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

 

 

처음에 문제만 보고 그냥 다익스트라로 푸는 문제인줄알았는데 계속 시간초과났다.

 

1. (0, 0)부터 시작 -> 이미 더 빠르게 지나온 기록이 있으면 continue

2. 현재 칸이 다음 칸보다 작으면 버튼 올려서 칸 맞춰주기

3. 최솟값 갱신

 

# 실패 코드

# 다익스트라 - 시간초과

from heapq import heappop, heappush

# 1. A[a][b] > A[c][d]
# 2. 1 <= i, j < n : A[i][j+1] , A[i+1][j]
# 3. 1 <= i < n , j ==n : A[i][j+1]
# 4. 1 == n, 1 <= j < n : A[i+1][j]
# 버튼 누르면 1원의 비용

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
visited = [[float('inf')] * n for _ in range(n)]
visited[0][0] = 0
heap = [(0, 0, 0)]

while heap:

    button, r, c = heappop(heap)

    if (r, c) == (n-1, n-1):
        print(button)
        break

    if button > visited[r][c]:
        continue

    for di, dj in [(1, 0), (0, 1)]:
        nr, nc = r + di, c + dj

        if not (0 <= nr < n and 0 <= nc < n):
            continue

        if arr[r][c] > arr[nr][nc]:
            next_button = button

        else:
            next_button = button + (arr[nr][nc] - arr[r][c]) + 1

        if next_button < visited[nr][nc]:
            visited[nr][nc] = next_button
            heappush(heap, (next_button, nr, nc))

 

 

계속 안풀려서 dp로 풀어야하나 하고 바꿨는데 통과됐다. 엄청 느렸지만..

 

1. (0, 0) 초기화

2. 위 아래 비교해서 더 버튼 적게 누른 쪽 저장

 

# 성공 코드

# dp

import sys
input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
dp = [[float('inf')] * n for _ in range(n)]
dp[0][0] = 0

for i in range(n):
    for j in range(n):

        if (i, j) == (0, 0):
            continue

        if 0 <= i-1 < n:
            up = dp[i-1][j] + max(0, arr[i][j] - arr[i-1][j] + 1)
        else:
            up = float('inf')

        if 0 <= j-1 < n:
            left = dp[i][j-1] + max(0, arr[i][j] - arr[i][j-1] + 1)
        else:
            left = float('inf')

        dp[i][j] = min(up, left)

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

 

 

 

다익스트라처럼 생긴 문제 중에 시간초과가 날 줄 몰랐는데 방심했다~

앞으론 시간복잡도 생각하고 설계 먼저 하고 푸는 연습을 해야겠다