Bin_S+StudyRoom

• 문제

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0] × B[0] + ... + A[N-1] × B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

• 입력

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

• 출력

첫째 줄에 S의 최솟값을 출력한다.

• 예제 입력

5
1 1 1 6 0
2 7 8 3 1

3
1 1 3
10 30 20

9
5 15 100 31 39 0 0 3 26
11 12 13 2 3 4 5 9 1

• 예제 출력

18

80

528

• 접근방식

A의 가장 작은수 * B의 가장 큰수 순으로 구하면 된다 즉, A를 오름차순, B를 내림차순으로 정렬하면 간단하게 해결되지만 문제의 조건인 B를 재배열하지 말라는 것을 지키려한다.

B에서 가장 큰수의 인덱스를 구해서 해당 인덱스의 요소를 식에 대입하면 된다. 이렇게 하면 재배열은 아니니깐..?? A를 재배열 하려면 결국 B의 요소들과 비교해야하는데 따로 저장해두는거 아니면 답이 없다고 생각한다.

• 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, result;
int a[54], b[54];

int main()
{
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    for (int i = 0; i < n; i++)
    {
        cin >> b[i];
    }

    // 단순히 a는 오름차순, b는 내림차순으로 풀 수 있으나
    // 문제에서 b는 재배열하지 말라는 것을 지켜보기
    // 1. a를 먼저 오름차순 정렬
    sort(a, a + n);
    int maxindex = 0;
    int bsize = sizeof(b) / sizeof(b[0]);
    for (int i = 0; i < n; i++)
    {
        // 2. b의 가장 큰 수의 인덱스를 구해서
        maxindex = max_element(b, b + bsize) - b;
        // 3. 식에 대입하기
        result += (a[i] * b[maxindex]);
        // 4. 사용한 b의 가장 큰수는 초기화
        b[maxindex] = 0;
    }

    cout << result;
    return 0;
}

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