[코드트리 챌린지] 2주차 - DP

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

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

 

정수 사각형 최솟값의 최대

문제

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가 되며, 더 크게 답을 만들 수가 없습니다.

 

제한

시간제한: 1000ms
메모리 제한: 80MB

 

---

풀이

시작점 (0, 0)과 0번째 열과 행을 초기화합니다. 0번째 행은 자기 자신과 바로 위의 값 중 작은 값으로 초기화하고, 0번째 열은 자기 자신과 왼쪽의 값 중 작은 값으로 초기화합니다.

 

(1,1)부터 (n-1, n-1)까지 연산을 수행합니다. 자신의 왼쪽, 위의 값 중 큰 값과 자기 자신을 비교하여 작은 값을 dp 배열에 저장합니다.

 

최종적으로 dp[n-1][n-1]의 값을 출력합니다.

 

점화식
dp[i][j] = min(max(dp[i-1][j], dp[i][j-1]), arr[i][j])

코드

let n = Int(readLine()!)!
var arr = [[Int]]()
var dp = Array(repeating: Array(repeating: 0, count: n), count: n)
var minValue = 0

for _ in 0..<n {
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

dp[0][0] = arr[0][0]

for i in 1..<n {
    dp[i][0] = min(dp[i-1][0], arr[i][0])
}

for j in 1..<n {
    dp[0][j] = min(dp[0][j-1], arr[0][j])
}

for i in 1..<n {
    for j in 1..<n {
        dp[i][j] = min(max(dp[i-1][j], dp[i][j-1]), arr[i][j])
    }
}

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