[프로그래머스 / C++] 최솟값 만들기

문제

최솟값 만들기 : 문제 링크

---

문제 분석

• 길이가 같은 배열 A, B 두개가 있다. 각 배열은 자연수로 이루어져 있다. 배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱한다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더한다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표이다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없다.) 예를 들어 A = [1, 4, 2], B = [5, 4, 4]라면

  • A에서 첫번째 숫자인 1, B에서 첫번째 숫자인 5를 뽑아 곱하여 더한다. (누적된 값 : 0 + 5(1x5) = 5)
  • A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더한다. (누적된 값 : 5 + 16(4x4) = 21)
  • A에서 세번째 숫자인 2, B에서 두번째 숫자인 4를 뽑아 곱하여 더한다. (누적된 값 : 21 + 8(2x4) = 29)

• 즉, 이 경우가 최소가 되므로 29를 return 한다. 배열 A, B가 주어질 때 최종적으로 누적된 최솟값을 return 하는 solution 함수를 완성

• 제한 사항

  • 배열 A, B의 크기 : 1,000 이하의 자연수
  • 배열 A, B의 원소의 크기 : 1,000 이하의 자연수

• 입출력 예

A	B
[1, 4, 2]	[5, 4, 4]
[1, 2]	[3, 4]

• 오름차순, 내림차순 정렬을 위해 sort() 함수를 사용하므로 algorithm 헤더를 include.
• 누적값을 저장할 정수형 변수 answer을 0으로 초기화. 누적합을 최소로 만들려면 배열 A의 가장 작은 수와 B의 가장 큰 수를 순서대로 곱해야 함. 따라서 sort() 함수를 사용하여 A를 오름차순으로, B를 내림차순으로 정렬. for loop를 통해 A의 첫번째 원소부터 마지막 원소까지 순환하고, 동일한 인덱스 위치의 A, B의 원소를 곱한값을 answer에 더하여 저장. loop 탈출 후, 최종적으로 저장된 anwer을 return

algorithm 헤더의 sort() 함수 사용법
void sort(T start, T end, Compare comp); //comp 인자가 공란이면 오름차순 정렬

• sort(v.begin(), v.end(), compare); // 사용자 정의 함수 사용
• sort(v.begin(), v.end(), greater<자료형>()); // 내림차순
• sort(v.rbegin(), v.rend()) // 내림차순
• sort(v.begin(), v.end(), less<자료형>()); // 오름차순

---

풀이

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> A, vector<int> B)
{
    int answer = 0;
    
    sort(A.begin(), A.end());
    sort(B.rbegin(), B.rend());
    for(int i = 0; i < A.size(); ++i) {
        answer += A[i] * B[i];
    }
    return answer;
}