[코드트리 챌린지] 6주차 - 동적계획법(DP)2

2주차를 하고나서 연휴에 열심히 놀고 ^^ 회사에서 플젝하다보니 이렇게 시간이 지나버렸고 6주차가 되어버렸다 ㅎㅎㅎ

다행히 현상유지 해버렸다 휴

그래도 먼가 까먹지 않고 다시 이 챌린지를 쓰는 나 자신 칭찬 ^^

 

당연하게도 저번에 막힌 부분을 공부하지 않았기 때무네?

똑같은 부분을 또 틀렸는데 솔직히 한 1분만 더 있으면 디버깅하고 풀었을 거 같아서 아숩다💦

아무튼 하지만 이 점화식 문제에 조금 더 익숙해져서 다행히 메모리초과, 시간초과없이 스무스하게 풀었다💨

 

보상이 끊겼기 때문에 열린 거 3문제? 중에 제일 어려웠던 거

https://www.codetree.ai/missions/2/problems/maximin-path-in-square?&utm_source=clipboard&utm_medium=text

 

 

이 문제 또한 격자 안에서 1칸씩 전진하는 문제지만,

방향이 오른쪽, 아래 그러니까 열과 행이 +1 되는 방향이 아니라는 것이 포인트✨

Sol 1

이 문제는 아래에서 위, 오른쪽에서 왼쪽으로, 열과 행이 -1 되는 방향으로 생각하면 쉽게 풀 수 있다.

 

Sol 2 

경로에 대해 단순히 합을 구하는 문제가 아니기 때문에 어떤 식으로 숫자를 배정할지가 아이디어의 핵심이었다.

" 작은 문제가 먼저 풀려있다는 가정 " 을 생각해보면,

계산하고자 하는 cell과 그 cell의 아래, 오른쪽 cell을 비교하여 경로의 최소숫자가 최대가 될 수 있도록 계산하고자 하는 cell의 값을 바꾼다

1) 그 cell의 아래, 오른쪽 cell을 비교하여 최대값 선택 - 목적지부터 시작된 경로중에 최소숫자가 최대인 경로를 선택

2) 계산하고자 하는 cell과 1)의 값을 비교하고 최소값을  선택 - 그 자신이 해당 경로의 최소숫자가 되는 것

 

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

def initialize() :
    for i in range(n-2, -1, -1) :
        grid[i][n-1] = min(grid[i][n-1], grid[i+1][n-1])
    for j in range(n-2, -1, -1) :
        grid[n-1][j] = min(grid[n-1][j], grid[n-1][j+1])

initialize()

def calculate() :
    for i in range(n-2, -1, -1) :
        for j in range(n-2, -1, -1) :
            grid[i][j] = min(max(grid[i+1][j], grid[i][j+1]),grid[i][j])

calculate()

print(grid[0][0])

 

n열과 n행은 무조건 한 방향으로만 접근 할 수 있기 때문에 초기조건으로 설정할 수 있다 (메모리 및 시간 최소화에 핵심)

 

어떤분은 메모리가 획기적으로 작으시던데 어떻게 푸셨는지 궁금

 

깔끔하게 해결했으니 다시 남은 챌린지💎