실력진단

ㅠㅠ 다시 점수가 떨어졌다. DP 문제를 못풀었는다... 분명 로직이 맞는데 dp 배열이 전부 채워지지 않아 시간초과로 탈락....

조금 아쉽지만, 다음엔 통과하기를 바라며...!

문제풀이

실력진단에서 떨어진 문제 유형은 지난번에 풀어봤기 때문에 이번엔 조금 꼬아놓은 문제로 가져왔다.
문제: https://www.codetree.ai/missions/2/problems/minimax-path-in-square?&utm_source=clipboard&utm_medium=text

처음 이런 유형의 문제를 봤을 때 문제 이해조차 안갔다.
최대로 하는 최소...?

결국 도착지점까지 가는 수많은 경로들의 최댓값 중 최솟값을 구하란 문제다.

맨 위와 맨 왼쪽은 max 를 통해 최댓값을 세팅하고 시작한다.

n = int(input())

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

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

for j in range(1, n):
    dp[0][j] = max(dp[0][j-1], grid[0][j])


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


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

그리고 가장 중요한 점화식을 해석하자면,
직전 최댓값들을 비교해 (dp[i-1][j], dp[i][j-1]) 둘 중 최솟값을 먼저 갖고 오고 그 다음 grid[i][j] 와 비교해 둘 중 최댓값을 가져온다.

이게 말로는 설명이 안되는데, 직접 점화식을 따라 계산해보면 이해가 된다.

바빠욧....

요즘 너무 바빠서 연습을 못했더니 아는 문제도 틀린는것 같다 ㅠㅠ
조금이라도 다시 힘내보자