[일반] D번 정해 뭐임?

[익명(210.103)]

5000까지 카운트 배열이랑 5000초과는 따로 {totalsum, #odd, #even} 저장해서 비벼서 풀었음. O(N^2)

[EN_SA(encludingsalt)]

D : ||sum(a_i)가 5000이하라는 추가 조건을 캐치하셔야 합니다. 그리고 문제에서 주어진 조건으로 공을 나누는 건, 가장 많은 공과 전부 매칭하고 나머지는 나머지끼리 매칭하면 됩니다(항상 서로 다른 짝이 남도록 둘 수 있습니다. 웰노운임). 이제 공의 개수에 대해서 정렬한 뒤, dp[i][j]는 [1..i] 범위에서 부분합이 j인 집합들의 value의 합으로 두면, dp[i][j] = cnt[i-1][ j-a[i] ] * (a[i] + max(0, (j-a[i]+1)/2)가 됩니다. cnt도 같이 관리해주면 해결가능합니다.||

[익명(211.36)]

또나만모르는웰노운이야 - dc App

[익명(182.231)]

정렬하면 현재 고려하는 색깔이 최대 공을 가진 색깔이니까 현재 고려하는 색을 포함하는 경우의 수를 구해서 답에 더할 수 있음 dp[i] = 이전까지 색의 공들로 i개의 공을 뽑는 경우의 수 라고 저장하고 dp배열 관리하면 됨

[익명(218.147)]

ㄱㅅㄱㅅ. 정해 예쁜데 추가 조건 안봐서 5000초과 따로 관리하느라 뻘짓 했네요;;

[익명(218.147)]

생각해보니 모듈러 홀수라 풀이가 틀렸네;;

[익명(118.235)]

백준이였으면 골드 4 정도할 dp였네 영어가 문제다.