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

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

 

유사한 문제: 정수 사각형 최댓값의 최소

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

 

 

문제 

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

 

입력 형식 

• 첫째 줄에는 N이 주어집니다.
  • 1≤N≤100
  • 1≤ 행렬에 주어지는 숫자 ≤1,000,000
• 두 번째 줄 부터 N개의 줄에 각각 각 행에 해당하는 N개의 정수 값이 공백을 사이에 두고 주어집니다.

 

출력 형식 

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

 

입출력 예제 

예제1 

입력:

3
5 2 3
3 2 1
1 2 4

출력:

2

 

예제 설명 

 

첫 번째 예제의 경우 다음과 같이 이동하면 지나는 경로에 적혀있는 숫자들 중 최솟값이 2가 되며, 더 크게 답을 만들 수가 없습니다.

 

 

 

다시말해 설명하자면 " 거쳐간 위치에 적혀있는 숫자들 중 최솟값을 최대로 하는 프로그램"의 의미는 

거쳐가는 위치 [5,2,2,4] 중에 최솟값을 최대로 하게 하라는 말

 

---

import sys
sys.stdin=open('input1.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] = min(dp[i-1][0], board[i][0])
    
    # 최상단 행의 초기값을 설정해줍니다.
    for j in range(1, n):
        dp[0][j] = min(dp[0][j-1], board[0][j])

    for i in range(1, n):
        for j in range(1, n):
        	# board[i][j] 값이 최소인게 더 중요 
            dp[i][j] = min(max(dp[i-1][j], dp[i][j-1]), board[i][j])
    
    print(dp[n-1][n-1])