[Code Tree] 정수 사각형 최댓값의 최소 [Python]

문제

https://www.codetree.ai/ko/trails/complete/curated-cards/test-minimax-path-in-square/description

정수 사각형 최댓값의 최소 설명 | 코드트리

 

---

풀이

문제 요약

주어진 N * N 행렬에 대해 (1, 1)에서 오른쪽/아래로만 이동하며 (N, N)까지 도달하는 경로 중 거쳐간 위치의 최대 비용이 최소가 되도록 하자.

아이디어

점화식은 다음과 같다.

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

현재 위치 (i, j)보다 (i - 1, j), (i, j - 1) 중 큰 비용이 있다면 이를 선택하게 된다. 따라서, (i - 1, j), (i, j - 1)중에서는 최소 비용을 선택하면 되기 때문이다.

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

# Please write your code here.

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

dp[1][0] = grid[1][1]
for i in range(1, N + 1):
    for j in range(1, N + 1):
        dp[i][j] = max(grid[i][j], min(dp[i - 1][j], dp[i][j - 1]))

print(dp[N][N])

풀이시간

5분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/code-tree/Algorithm Intro/DP I/12 정수 사각형 최댓값의 최소(test-minimax-path-in-square).py

problem-solving/code-tree/Algorithm Intro/DP I/12 정수 사각형 최댓값의 최소(test-minimax-path-in-square).py at main