다이나믹 프로그래밍 (2) 썸네일형 리스트형 [문제풀이] 백준 1932번 정수 삼각형 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제풀이 n = int(input()) t = [] for i in range(n): t.append(list(map(int, input().split()))) k = 2 for i in range(1, n): for j in range(k): if j == 0: t[i][j] = t[i][j] + t[i-1][j] elif i == j: t[i][j] = t[i][j] + t[i-1][j-1] else: t[i][j] = max(t[i-1][j-1], t[i - 1][j]) + t[i][j] k += 1 print(max(t[n-1.. [알고리즘] Dynamic Programming Dynamic Programming Dynamic Programming에서 Dynamic programming은 딱히 의미 없는 용어이다. 그냥 Dynamic, 멋있어서 붙인 용어라고 한다. Dynamic programming은 Optimal Substructure(최적 부분 구조)와 Overlapping Subproblem(중복되는 부분 문제)를 만족할때 자주 사용한다고 한다. Optimal Substructure는 큰 문제를 작은 문제로 나누어 작은 문제를 해결하여 결과를 도출하고 그 결과를 모아 큰 문제를 해결할 수 있는 문제를 의미한다. Overlapping Subproblem은 동일한 문제를 반복적으로 해결하는 문제이다. Fibonacci Sequence 대부분 동적 프로그래밍 예제로서 피보나치.. 이전 1 다음
