반응형 BOJ19121 BOJ 1912 (C++) 1. 문제 2. 아이디어 Dynamic Programming은 점화식만 세우면 80~90%는 풀었다고 할 수 있다. 연속된 몇 개의 수의 합 중 최댓값을 구하는 문제이므로 현재값과 누적된 값 + 현재값 중 어떤 것이 더 큰지 비교해보면 답을 구할 수 있을 것이다. -> 만약 누적된 값에 현재값을 더한 것보다 그냥 현재값이 더 크다면 현재값부터 다시 더해나가는것이 더 큰 값이 될것이다 라는 아이디어이다. 점화식을 세우면 DP[i] = max(arr[i], DP[i-1] + arr[i]) 이고 예제 1의 케이스로 보면 arr [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 10 -4 3 1 5 6 -35 12 21 -1 DP [0] [1] [2] [3] [4] [5] [6] [7] [.. 2020. 11. 29. 이전 1 다음 반응형
