[Algorithm] 동적계획법(Dynamic programming) - Brute Force, Kadane’s Algorithm
#동적계획법(Dynamic programming) - 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 (wikipedia) - Bottom-Up 적 방법 #동적계획법 예제 - nm선 자르기 #nm의 선을 1m나 2m 자르는 방법의 수 #1m 선의 경우 #[1,1,1] => 1가지 #dy[1]=1 #2m 선의 경우 #[1,1,1],[2] => 2가지 #dy[2]=2 #3m 선의 경우 #[1,1,1] => 1가지 #[1,1,1],[2] => 2가지 #1가지(1m선의 경우) + 2가지(2m선의 경우) = 3가지 #dy[3]=3 #4m 선의 경우 #2가지(2m선의 경우) + 3가지(3m선의 경우) = 5가지 #dy[4]=5 n = int(input()) dy=[0]*(n+1) #배열을 만듦 dy[1]=..
2020. 9. 6.
