https://www.acmicpc.net/problem/13029
Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net계속 고민하고 있는데...제 자그마한 머리로는 O(N^2*10000)풀이밖에 떠오르지가 않아요....
누적합으로 각 구간의 합을 구한 다음에 각 구간에서 냅색을 이용해 그 구간의 합의 1/2배를 고르는 방법이 있는지를 보는 식으로 생각했는데....
풀이를 찾아봐도 나오지를 않고 답답하네요 ㅠㅠ
dp[n][s] = n개 까지 봤을 때 합이 s가 되는 경우의 수 해서 dp[i][0]들 합 더해주면 됨 다만 연속 부분합이니 여태 하나도 안 고른 경우도 고려해줘야 함 그러니까 dp[i+1] 배열 갱신할 때 dp[i][0]에 1더해서 계산해야 됨
오옹 감사합니다!!
덕분에 풀었어요!! 감사합니다~