[코드트리 챌린지] 정수 사각형 최소 합

코딩 테스트

코드트리애호가 2023. 10. 4. 16:27

하..

DP 점화식에서 또틀렸다..

아니 1,1 부터 N,N 나오고

N,1 에서 N,1 나오더니 이번에는

왠

123

이런 행렬이 나오더니

3부터 가장왼쪽으로 갈때 최대값을 구하라고해서 ;;

저 가장 오른쪽 끝 3부터 가장아래 1 까지 점화식을 짜다가 시간 오버..;;;;;;;;;;;;;;;;;;;;;;

이거 실제로 나오면 구현하다가 꽤 애먹을꺼같다..

수학적 지식이 필요해버려서 굉장히 곤란하다 이거 ㅠㅠㅠㅜㅜㅠㅠㅜ아아아악

DP때문에 막힌게 도대체 몇번인지;;

그래서 복습하려고 아래문제를 풀어봤다.

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

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

www.codetree.ai

항상 테투리 부분을 먼저 점화식을 세워서

바로 dp + maps 해서 만들어주고,

그나머지 부분을 반으로 자르거나 해서 완성해야한다.

반으로 잘라서 완성하는거 생각해보니 올해 1월부터 코드트리 쭉하면서

DP부분때 잘풀었던거같은데..

왜꼭 시간만 정해지면 갑자기 급해지면서 틀리는지모르겠다..

이제 슬슬 시간정해서 삼성코테기출문제도 풀어야겠다.

너무 무제한으로 8 시간으로 푸니까 이게 습관이 되는거같다.

정해진시간안에 풀게 빡집중하고.

vscode 등의 디버그 툴을 잘사용해서 엣지케이스(특이한) 까지 검증하기가

목표다.

그리고 풀엇다고 다시 안풀어보지말고 다시풀어보며 알고리즘을 더 깔끔하게 정리해보자.

n = int(input())

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

dp = [ [0]*n for _ in range(n)]

dp[0][n-1] = maps[0][n-1]

for i in range(n-1,0,-1) :

dp[0][i-1] = dp[0][i] + maps[0][i-1]

for j in range(1,n) :

dp[j][n-1] = dp[j-1][n-1] +maps[j][n-1]

for i1 in range(1,n):

for j1 in range(n-2,-1,-1) :

dp[i1][j1] = min(maps[i1][j1]+dp[i1-1][j1],maps[i1][j1]+dp[i1][j1+1])

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

#for kk in dp :

# print(*kk)