26607. 시로코와 은행털기

소신발언

 

시로코라는 캐릭터 처음 봤는데 내 취향 아님

 

26607번: 시로코와 은행털기

---

흠흠.. $a+b=x$가 일정한 정수 쌍이 $n$개 주어진다. 그 중 $k$개를 골라서 $\sum_{i=1}^{k}{a_{i}} \times \sum_{i=1}^{k}{b_{i}}$를 최대화해야 한다.

 

$b=x-a$로 나타낼 수 있으므로 주어진 식을 전개하면 $\sum_{i=1}^{k}{a_{i}} \times \sum_{i=1}^{k}{(x-a_{i})}$이고, $\sum_{i=1}^{k}{a_{i}}=A$로 치환하면 $A(kx-A)$로 정리할 수 있다. 따라서 $A$만 알면 주어진 식의 값을 구할 수 있다.

 

이제 주어진 식의 값을 최대로 만드는 $A$를 찾자. $n$과 $k$가 커서 브루트 포스는 불가능하고, dp를 써야 한다. 처음 풀 때는 현재 고르는 사람의 인덱스($i$)와 지금까지 고른 사람의 수($j$) 2개의 상태만 생각하는데(나도 그랬다), $j$가 같아도 고른 사람들의 능력치의 합(=A)은 다를 수 있다. $j$명을 고르는 경우의 수가 많기 때문이다. 

 

따라서 $j$만으로는 모든 상태를 나타낼 수 없고, 고른 사람들의 능력치의 합을 나타내는 $p$를 추가해야 한다. 완성된 dp 식의 정의는 다음과 같다.

 

$dp[i][j][p]$: 현재 $i$번 사람을 고르는 중이고, $i$번을 선택하거나 선택하지 않은 결과 고른 사람의 수가 $j$명이고, $j$명의 능력치의 합이 $p$인 경우가 존재하는가?

 

자료형은 bool이다. $i$번까지 총 $j$명을 골라서 능력치의 합이 $p$인 경우가 존재하면 true, 아니면 false이다.

 

이제 dp 테이블을 채우면 된다. 기저 state는 $dp[i][0][0]=true$, $dp[i][1][a_{i}]=true$이다. 이제 각 $(i,~j,~p)$ 쌍에 대해 $i$번 사람을 고르는 경우와 고르지 않는 경우를 고려하여 $dp[i][j][p]$를 계산하면 된다.

 

갱신 순서를 잘 바꾸면 $i$를 없앨 수도 있을 것 같다. 하지만 여백이 부족하므로 이 부분은 적지 않겠다.

---

2차원으로 하려다가 3번 틀림 ㅠ