[코드트리] 정수 사각형 최솟값의 최대 , python 문제 풀이

내일이면 파이썬 방학 캠프가 끝이 나네요. 마지막은 마무리 시험을 보며 끝이 납니다. 2주밖에 되지 않았지만 파이썬 수업을 한 번도 들어보지 않은 입장으로 정말 익숙해졌다고 생각해요. 알고리즘 쪽으로나 구현 쪽으로나 파이썬과 친해진 게 느껴집니다. 아주 만족합니다. 오늘은 마지막으로 동적 계획법 문제를 하나 가져왔습니다. 코드 트리를 주제로는 마지막 포스팅이 될 수도 있겠네요.

---

문제

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

입력 형식

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

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

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

출력 형식

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

입출력 예제

예제 1

입력:

3
5 2 3
3 2 1
1 2 4

 

출력:

2

 

예제 2

입력:

3
4 3 2
3 4 5
4 2 8

 

출력:

3

 

예제 설명

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

처음에 보면 뭔 소리인지 잘 몰랐는데요 1,1에서 n, n까지 가는데 모든 경로가 있겠죠? 그 경로도 하나의 최솟값을 가지고 있을 겁니다 그 모든 경로의 최솟값만 모아 놨을 때 그 최솟값 속에 가장 큰 수는 무엇인가 하는 문제입니다.

---

코드

n = int(input())

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

#가는 경로중 무조건 최소값이 있을텐데 그 최소값중 가장 큰것은 무엇인가?


def init():
    
    dp[0][0]=nums[0][0]

    for i in range(1,n):
        dp[i][0] = min(dp[i-1][0], nums[i][0])
        dp[0][i] = min(dp[0][i-1], nums[0][i])

init()

for i in range(1,n):
    for j in range(1,n):
        dp[i][j] = min(max(dp[i-1][j] , dp[i][j-1]), nums[i][j])

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