⭐⭐⭐[코드트리] 정수 사각형 최댓값의 최소

https://www.codetree.ai/missions/2/problems/minimax-path-in-square/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

유사 문제: 정수 사각형 최솟값의 최대

[코드트리] 정수 사각형 최솟값의 최대

 

문제 

N×N 행렬이 주어졌을 때, (1,1)에서 시작하여 오른쪽 혹은 밑으로만 이동하여 (N,N)으로 간다고 했을 때 거쳐간 위치에 적혀있는 숫자들 중 최댓값을 최소로 하는 프로그램을 작성해보세요.

입력 형식

첫째 줄에는 N이 주어집니다.

두 번째 줄 부터 N개의 줄에 각각 각 행에 해당하는 N개의 정수 값이 공백을 사이에 두고 주어집니다.

• 1≤N≤100
• 1≤ 행렬에 주어지는 숫자 ≤1,000,000

출력 형식

가능한 경로의 숫자들 중 최댓값의 최솟값을 출력합니다.

 

입출력 예제

예제1

입력:

3
1 4 3
3 4 5
5 4 2

 

출력:

4

 

 

 

---

 

이 문제에서는 동일한 상태를 정의하기 위한 요소로 
- 시작점에서 출발하여 마지막으로 방문한 위치,
- 선택된 경로에서의 최댓값 
두 가지를 생각해 볼 수 있다. 

문제에서 최댓값의 최소를 구하라고 하였으므로 
'시작점에서 출발하여 마지막으로 방문한 위치'가 동일한 경우
'선택된 경로에서의 최댓값'이 최소가 되어야 한다는 점을 이용하여 
점화식을 세워보면 문제를 해결 할 수 있다. 

---
알고리즘 

시작점에서 출발하여 마지막으로 방문한 위치가 동일한 상황에서, 
해당 위치까지 이동한 경로에 적힌 숫자들의 최댓값이
같은 경로 'path1'과 'path2'가 있다고 가정해 보자.

해당 위치에서 도착점까지 방문하는 경로를 잘 선택해서 전체 경로에 적힌 숫자의 최댓값을 최소화 하려는 관점에서 바라보았을 때, 
'path1'과 'path2'는 동등한 상황이라고 생각할 수 있습니다.
왜냐하면 해당 문제에서는 '마지막으로 방문한 위치'와 '이동한 경로상의 최댓값'이 일치하는 경우, 
그 이후의 입장에서 봤을 때 동일한 상황으로 간주할 수 있기 때문이다. 

문제의 조건에서 "선택된 경로의 최댓값을 최소화'하라고 하였으므로, 
마지막으로 방문한 위치가 같은 경우 해당 경로 상의 최댓값은 클수록 좋다고 판단할 수 있다. 
이 때 dp[i][j]를 '(0,0)에서 시작해서 (i,j)까지 이동했을 때의 최댓값 중 최소'라고 정의 해봅시다. 
문제에서 아래 방향과 오른쪽 방향으로만 이동이 가능하다고 하였으므로 dp[i][j] 값을 구하기 위해서는 다음의 두가지를 고려해보아야한다.

1. 직선 경로의 위치에서 아래 방향으로 이동하여 (i,j)로 오게 되는 경우 
이 경우 '경로상의 최댓값' 중에 최소는 '직전 경로까지의 최댓값' 중 최소인 dp[i-1][j]에 해당 위치의 숫자인 num[i][j] 중에 최댓값을 구해주면 된다.

2. 직전 경로의 위치에서 오른쪽 방향으로 이동하여 (i,j)로 오게 되는 경우 
이 경우 '경로상의 최댓값' 중에 최소는 '직전 경로까지의 최댓값' 중 최소인 dp[i][j-1]에 해당 위치의 숫자인 num[i][j] 중에 최댓값을 구해주면 된다. 

정리해보면 해당 점화식은 dp[i][j] = max(min(dp[i-1][j],dp[i][j-1]), board[i][j])가 된다.

 

---

import sys

sys.stdin=open('input.txt', 'r')

if __name__=="__main__":

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

    dp = [[0 for _ in range(n)] for _ in range(n)]
    dp[0][0] = board[0][0]

    # 좌측 첫 열에 가장 큰 값
    for i in range(1,n):
        dp[i][0] = max(dp[i-1][0], board[i][0])     # 계속 최댓값을 기록해줌 
    
    # 최상단 첫 행에 가장 큰 값
    for i in range(1,n):
        dp[0][i] = max(dp[0][i-1], board[0][i])     # 계속 최댓값을 기록해줌 
    
    for i in range(1,n):
        for j in range(1,n):
            # 계속 최댓값을 기록해줌 -> max 
            # (i,j)의 좌측의 최대값과 상측의 최대값 중 최소값과 board(i,j) 중 최대값 업데이트
            dp[i][j] = max(min(dp[i-1][j],dp[i][j-1]), board[i][j])
    
    print(dp[n-1][n-1])