말랑한 하루

※ 소스코드는 각 문제 설명 하단에 를 통해 확인하실 수 있습니다. [gold5, 11398 연속합2] - 다이나믹 프로그래밍(DP) 수를 제거하지 않은 경우와 제거한 경우를 각각 sum[i][0], sum[i][1]배열에 저장한다 할 때 수를 제거하지 않는 경우엔 연속된 구간의 합이 수열의 다음 수보다 작은 경우, 수열의 다음수 부터 새로운 구간을 시작하게 된다 이를 통해 연속합을 저장하는 sum[i][0]배열의 값은 max(sum[i - 1][0] + num[i], num[i])라는 점화식을 끌어낼 수 있다 현재를 기준으로 수를 제거한 경우를 생각해보면 1) 현재를 제거하는 경우: sum[i - 1][0] 2) 이미 제거된 경우: sum[i - 1][1] + num[i] 이와 같은 두 식이 나오게되고..

※ 소스코드는 각 문제 설명 하단에 를 통해 확인하실 수 있습니다. [sliver 1, 1309 동물원] - 다이나믹 프로그래밍(DP) N번째 줄에 사자를 배치할 수 있는 경우는 다음과 같다. (미배치(0), 왼쪽(1), 오른쪽(2)) 1) 모두 없는 경우: 왼쪽, 오른쪽, 미배치 → dp[n][0] = dp[n-1][0] + dp[n-1][1] + dp[n-1][2]; 2) 왼쪽 칸에 있는 경우: 오른쪽, 미배치 → dp[n][1] = dp[n-1][0] + dp[n-1][2]; 3) 오른쪽 칸에 있는 경우: 왼쪽, 미배치 → dp[n][2] = dp[n-1][0] + dp[n-1][1]; 이를 종합해보면 for(int i=2;i