BOJ 13448 SW 역량 테스트

 

문제 링크 : https://www.acmicpc.net/problem/13448

13448번: SW 역량 테스트

 

 

i 번째 문제와 관련된 \(M_i, R_i, P_i \) 를 묶어서 생각할 때,

\[ \frac{R_i}{P_i}\]

의 크기순으로 처리하면 문제가 해결된다.

 

왜? 어떻게 알았지?

 

이해를 돕기 위해 체비셰프 부등식(Chebyshev's Inequality) 부터 살펴보자.

 \( a_1 \le a_2 \le \cdots \le a_n \) , \( b_1 \le b_2 \le \cdots \le b_n \) 일 때,

\[  a_1b_n+a_2b_{n-1} + \cdots + a_nb_1 \le a_1 b_{\sigma(1)}+a_2b_{\sigma(2)} +\cdots+a_nb_{\sigma(n)} \le a_1b_1+a_2b_2+\cdots+a_nb_n   \]

이 성립한다. (물론 \(\sigma : \{1,2,\cdots\,n\} \rightarrow \{1,2,\cdots,n\}\) 는 일대일대응이고 수열의 각 항은 음수여도 괜찮다. )

 

이름에 주눅들지 않고 생각해보면 누구나 다 아는 부등식이다.

예를 들어 보자.

서로 다른 지폐 3 종류를 각각 5 장, 3 장, 1 장을 선택할 수 있다고 하자.

세 종류의 지폐가 5 만원권, 1 만원권, 1 천원권 이라면 어떤 것을 5 장 선택할 것인가를 묻는 것이다.

 

 

결국 크기 순으로 짝지어서 더하는게 가장 크다는 말인데...

 

모양새를 갖춘 증명을 써보자.

 

\(\sigma\) 가 항등함수가 아니라면 \(b_{\sigma(i)} >b_{\sigma(i+1)} \) 인 i 가 존재한다. 그리고, 

\[ a_1 b_{\sigma(1)}+\cdots+a_i b_{\sigma(i)} + a_{i+1} b_{\sigma(i+1)}+\cdots+a_nb_{\sigma(n)}  \le a_1 b_{\sigma(1)}+\cdots+a_i b_{\sigma(i+1)} + a_{i+1} b_{\sigma(i)}+\cdots+a_nb_{\sigma(n)}\]

가 성립한다. 우변에서 좌변을 빼면

\[ (a_{i+1} - a_i ) (b_{\sigma(i)} - b_{\sigma(i+1)} ) > 0 \] 

을 확인할 수 있다. 따라서 수열 b 를 재배열 했을 때 증가수열이 아니면 a와 짝지으면 언제나 더 큰 다른 짝짓기가 존재한다.

 

즉, 순서가 역전된 \(b_i > b_{i+1} \) 을 만나면 두 개를 위치를 바꾸어서 더 큰 값을 만들 수 있다.

이 과정을 반복해서 수열 b 의 모든 원소가 크기 순으로(증가하도록) 만들 수 있고, 그 때가 최대가 된다.

 

여기서 눈여겨 볼 것은  이웃하는 두 항의 어떻게 선택되어야 하는지를 판단할 수 있으면 전체에 대해 판단할 수 있다는 사실이다.

이웃하는 두 항의 비교를 반복함으로써 결과적으로 전체를 정렬하는 버블소트를 생각하면 어쩌면 자연스럽다.

 

 

본 문제로 돌아가자.

문제에서는 누적된 시간이 입력되어야 하기때문에 수열로 보면 체비셰프 부등식을 적용할 수 없지만...

 

우리가 구해야 하는 것은 다음 항들의 합이다.

\[ M_1-R_1*P_1 \]

\[ \cdots \]

\[ M_i -(R_1+\cdots+R_{i-1}+R_i)*P_i \]

\[M_{i+1}-(R_1+\cdots+R_{i-1}+R_i+R_{i+1}) * P_{i+1} \]

\[ \cdots \]

만약 

\[ \frac{R_i}{P_i} > \frac{R_{i+1}} {P_{i+1}} \]

이면 두 항을 

\[M_{i+1}-(R_1+\cdots+R_{i-1}+R_{i+1}) * P_{i+1} \]

\[ M_i -(R_1+\cdots+R_{i-1}+R_{i+1}+R_i)*P_i \]

바꾸고 원래의 식을 빼보자.

 

\( M_i ,  M_{i+1} \) 과 누적 시간 \(R_1 +\cdots + R_{i-1} \) 은 순서는 바뀌었지만 공통으로 등장하니 제거되고

\[ -R_{i+1}*P_i + R_i*P_{i+1} > 0\]

을 확인할 수 있다.

 

비단 이 문제만이 아니라 두 수열을 서로 짝지어 대소의 최적화를 원하는 많은 문제는

이웃하는 두 항에서 대소를 결정하는 요소를 찾는 문제

 

로 환원된다! (짝을 짓는 방식에 따라 수열 a, b의 각 원소의 값이 달라지지 않는다면...)

 

이 후의 과정은 routine 이다.

 

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

struct info{
    ll m,r,p;
    info() : m{0},r{0},p{0} {}
    info(ll m, ll r, ll p) : m{m},r{r},p{p} {}
    
    bool operator<(const info &rhs) const{
        return r*rhs.p < rhs.r*p;
    }
} arr[51];

int N, T;
ll dp[51][100001];

ll recur(int p, int t){
    if(p==N) return 0;
    
    ll &ret=dp[p][t];
    if(ret!=-1) return ret;
    
    if(t+arr[p].r <= T){
        ll tmp=arr[p].m-(t+arr[p].r)*arr[p].p;
        if(tmp>0)
            ret=max(ret, recur(p+1, t+arr[p].r)+tmp);
    }   
    ret=max(ret, recur(p+1,t)); 
    
    return ret;
}

int main(){
    scanf("%d%d", &N,&T);
    for(int i=0;i<N;i++) scanf("%lld", &arr[i].m);
    for(int i=0;i<N;i++) scanf("%lld", &arr[i].p);
    for(int i=0;i<N;i++) scanf("%lld", &arr[i].r);
    
    sort(arr, arr+N);
    for(int i=0;i<N;i++)
        for(int j=0;j<=T;j++)
            dp[i][j]=-1;
    
    printf("%lld\n", recur(0,0));
}