SY DevLog

2228번: 구간 나누기 N(1≤N≤100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1≤M≤⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야 www.acmicpc.net dp[n][m] : n개의 수를 m개의 구간으로 나누었을 때 최대 합 arr[i] : 입력받은 수들을 저장 n번째 수가 m번째 구간에 포함되어 있는지, 포함되어 있지 않는지 두 가지 경우로 나눌 수 있다. - n번째 수가 구간 m에 포함되지 않은 경우 : dp[n][m] = dp[n-1][m] n-1번째 수가 구간 m에 포함된 경우의 최대 합(dp[n-1][m])과 동일하다. - n번째 수가 구간 m에 포함된 경우 : dp[n][m] = max(d..

3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 누적합으로 문제를 해결하였다. 각각의 높이에 따라 석순과 종유석의 개수를 카운트하는 두 개의 배열 bot, top을 생성하였다. 예를 들어, 첫 번째 구간에서는 석순이 7개 존재하므로 bot[1] = 7 이 된다. 두 번째 구간에는 석순이 6개 존재하므로 bot[2] = 6 세 번째 구간에는 석순이 5개 존재하므로 bot[3] = 5 네 번째 구간에는 석순이 1개 존재하므로 bot[4] = 1 다섯 번째 구간에는 석순이 0개 존재하므로 bot[5] = 0 첫 번째 ..