# 백준 : 보물(1026)

문제

https://www.acmicpc.net/problem/1026

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_1026_treasure)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
#include <cmath>
using namespace std;

bool naerim(int a, int b) {
    return a > b;
}

int dp[51];

int main(void)
{
    vector<int> a, b;
    int count, value, index, result;
    cin>>count;
    
    for(int i=0; i<50; i++) dp[i] = 10101;
    
    for(int i=0; i<count; i++) {
        cin>>value;
        a.push_back(value);
    }
    for(int i=0; i<count; i++) {
        cin>>value;
        b.push_back(value);
    }
    
    sort(a.begin(), a.end(), naerim);
    index = 0;
    result = 0;
    for(int i=0; i<a.size(); i++) {
        for(int j=0; j<b.size(); j++) {
            if(dp[i] > a[i] * b[j]) {
                index = j;
                dp[i] = a[i] * b[j];
            }
        }
        result += dp[i];
        b[index] = 101;
    }
    cout<<result<<endl;
    
    return 0;
}

풀이

간단하게 생각하면, 한쪽은 오름차순 한쪽은 내림차순으로 해서 하나씩 곱하면되는데.
이 문제의 조건은 '한쪽은 정렬해도 되는데, 남은 한쪽은 하면 안되.' 였다.
백준 풀이보니까 그냥 답만 나오면 되므로 다들 둘다 정렬했던것 같은데, 나는 실력향상을 목적으로 하니까 문제 대로 한쪽만 정렬하는 방식으로 풀어보았다.

DP를 사용하면 되는데, 한쪽을 내림차순으로(큰수부터 작은수 순서대로) 정렬한 후에, 다른 한쪽의 첫번째 수부터 차례대로 비교해가면서 제일 작은 크기를 갖는 애를 찾아 DP에 넣어주면 된다.

중요한 것은 중복확인을 하면 안되므로, 다른 한쪽의 행렬에서 가져온 녀석은 제일 큰수 (문제에서는 100 이하의 수만 취급한다고 하였으므로 101)로 바꿔치기 해주면 된다.

DP로 문제를 접근하다니!! 실력의 늘어감이 느껴진다.