[Code Tree] 정수 사각형 차이의 최소 2 [Python]

문제

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-minimum-difference-on-the-integer-grid-2/description

정수 사각형 차이의 최소 2 설명 | 코드트리

 

---

풀이

문제 요약

주어진 N * N 행렬에 대해 (1, 1)에서 오른쪽/아래로만 이동하며 (N, N)까지 도달하는 경로에 적혀있는 수의 최댓값과 최솟값의 차이를 가장 작게 만들자.

아이디어

경로의 최대/최소값을 모두 기록하며, 두 수의 차를 최소화 해야한다.

점화식은 다음과 같다.

dp[i][j][k] : 현재 경로까지 가장 작은 값이 k일 때 경로 중 있었던 가장 큰 값 중 가능한 최솟값

즉 현재 위치(i, j)에 대해 이전 경로(i - 1, j), (i, j - 1)의 유효한 모든 k에 대해 최솟값을 가져와야 한다. 이전 경로의 k가 작을 때의 결과가 정답이 아닐 수 있기 때문이다.

N = int(input())
grid = [None] + [[0, *map(int, input().split())] for _ in range(N)]

# Please write your code here.

INF = int(1e10)
dp = [[[INF] * 101 for _ in range(N + 1)] for _ in range(N + 1)]

dp[1][1][grid[1][1]] = grid[1][1]
for i in range(1, N + 1):
    for j in range(1, N + 1):
        for k in range(1, 101):
            min_k = min(k, grid[i][j])

만약 이전 경로에 최솟값이 k인적이 없다면 초기값 INF가 그대로 전이된다

결과 부분에서 INF가 아님을 체크 후 결과를 확인하자.

            dp[i][j][min_k] = min(dp[i][j][min_k], 
                                max(grid[i][j], min(dp[i - 1][j][k], dp[i][j - 1][k])))

res = INF
for k in range(1, 101):
    if dp[N][N][k] != INF:
        res = min(res, dp[N][N][k] - k)
print(res)

풀이시간

30분

---

소스코드

problem-solving/code-tree/Algorithm Intro/DP I/11 정수 사각형 차이의 최소 2(challenge-minimum-difference-on-the-integer-grid-2).py at main · rogi-rogi/problem-solving

problem-solving/code-tree/Algorithm Intro/DP I/11 정수 사각형 차이의 최소 2(challenge-minimum-difference-on-the-intege