[코드트리 챌린지] 네번째 학습진단

오늘은 학습진단 중에 다른 일이 생겨서 시간이 부족했다.

그래서 6번째 문제를 다 풀지 못했다.

특히 문제만 보고 DFS로 풀면 되겠네 생각했다가

시간 초과로 틀렸었다.

아마 구현했던 방법의 시간 복잡도는

순열의 개수를 구하는 문제와 같은 O((2n)!/(n!*n!)) 일 것으로 보인다.

DP로 다시 풀려고 하다가 중단하게 되었는데, DP로 풀면 O(n^2) 이므로 더 빠르다

처음부터 DP로 접근해야겠다는 생각이 들도록 머릿속에 넣으면 좋을 것 같다.

 

유사 문제 풀이

https://www.codetree.ai/landing/level-test/6630/result/4?&utm_source=clipboard&utm_medium=text 

 

문제

오른쪽 혹은 아래쪽으로만 이동하여 (1,1)에서 (n,n)로 가는 '경로의 최솟값'을 최대로 하는 값을 도출하는 문제이다.

경로 중에선 큰 값을 가지는 경로가 선택되어야 하지만

현재 지나는 값과 비교할 땐, 현재 경로의 최솟값이 선택되어야 함을 주의하자.

코드

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

# 경로의 최솟값을 담을 dp
dp = [[0]*n for _ in range(n)]
dp[0][0] = arr[0][0]

# 첫 행과 첫 열을 먼저 채워준다.
for i in range(1,n):
    dp[i][0] = min(dp[i-1][0], arr[i][0])
    dp[0][i] = min(dp[0][i-1], arr[0][i])
    
# 오른쪽이나 아래쪽으로 이동하는 것임으로
# 위쪽이나 왼쪽에서 현재 위치로 연결된다.
# 즉 위쪽이나 왼쪽 값 중 큰 값을 선택해야 최솟값이 더 큰 경로를 선택하게 된다.
# 이제 그 값과 현재 위치 값을 비교하여 최솟값을 구해주면 된다.
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]), arr[i][j])

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

 

 

---

#코드트리 #코딩테스트 #코딩테스트실력진단