-
[동적 계획법] 정수 삼각형코딩 테스트/프로그래머스 2023. 3. 29. 20:07
문제 설명
https://school.programmers.co.kr/learn/courses/30/lessons/43105
문제 풀이
- 다이나믹 프로그래밍 문제
- 점화식: dp(i,j) = dp(i,j) + max( dp(i-1,j) , dp(i-1,j-1) )
- i,j의 기준을 아랫줄로 잡고 윗 줄에서 내려온 두 값 중 최댓값을 현재 위치에 더함
소스 코드(python)
def solution(triangle): answer = 0 n = len(triangle) for i in range(n): #밑에서 점화식을 계산할 때 j(세로)가 0번째 일때를 위해 맨 첫줄마다 0을 넣어줌 triangle[i]=[0]+triangle[i] dp = [[0]*(n+1) for i in range(n)] for i in range(n): for j in range(1,i+2): dp[i][j]=triangle[i][j] for i in range(1,n): for j in range(1,i+2): dp[i][j] = dp[i][j] + max(dp[i-1][j],dp[i-1][j-1]) return max(dp[n-1]) #맨 밑 줄 최댓값이 정답 if __name__=='__main__': t=[] for i in range(5): t.append(list(map(int,input().rsplit()))) print(solution(t))
'코딩 테스트 > 프로그래머스' 카테고리의 다른 글
[동적 계획법] 등굣길 (0) 2023.03.31 [DFS/BFS] 단어 변환 (0) 2023.03.30 [DFS/BFS] 네트워크 (0) 2023.03.30 [연습 문제] 최고의 집합 (0) 2023.03.29 [힙] 이중 우선순위 큐 (0) 2023.03.29