문제
https://www.acmicpc.net/problem/1026
a, b 두개의 배열이 있을 때, 같은 위치에 있는 값을 서로 곱했을 때 나오는 값이 최소가 되도록 a배열의 원소를 재배열 하는 문제
접근방식
a,b 두 배열은 0이거나 100이하의 자연수로만 구성된다.
answer = (a[i] * b[i]) + ... + (a[N-1] * b[N-1]) 이 최소가 되는 수를 구하자.
가장 쉽게 생각하면, a배열은 오름차순으로, b배열은 내림차순으로 정렬 후 서로 곱해주면 항상 최소가 된다. b배열은 재배열 하지 말라는 조건때문에 좀 헷갈렸는데... (체크할 수도 없는 조건이 왜 들어가 있는지...)
(풀이)
| 1 #include <iostream> 2 #include <algorithm> 3 #include <vector> 4 5 using namespace std; 6 7 int main() 8 { 9 int N, i, j, num; 10 vector<int> a; 11 vector<int> b; 12 int new_a[50]; 13 int max = -1; 14 int max_idx = -1; 15 int answer = 0; 16 17 cin >> N; 18 for (i = 0; i < N; i++) 19 { 20 cin >> num; 21 a.push_back(num); 22 } 23 for (i = 0; i < N; i++) 24 { 25 cin >> num; 26 b.push_back(num); 27 } 28 sort(a.begin(), a.end()); 29 for (i = 0; i < N; i++) 30 { 31 for (j = 0; j < N; j++) 32 { 33 if (b[j] > max) 34 { 35 max = b[j]; 36 max_idx = j; 37 } 38 } 39 answer += (max * a[i]); 40 b[max_idx] = -1; 41 max = -1; 42 } 43 cout << answer << endl; 44 return 0; 45 } |
a 배열은 오름차순으로 정렬을 하고, b배열은 max값을 찾아서 서로 곱하여 누적하는 방식으로 계산했습니다. 시간 복잡도는 a배열을 정렬하는 데 필요한 시간, 그리고 a배열의 매 원소마다 b배열을 뒤져서 max값을 찾아야 하므로 O(NlogN) + O(N^2) 시간이 소요된다고 볼 수 있겠습니다.
만약, 두 배열을 각각 정렬 후 곱한다고 하면 O(2 * NlogN + N) 이렇게 될 것 같은데, 두 번의 정렬과 한번의 루프 순회가 있으면 될 것 같습니다.
회고
b배열을 재배열 하지 말라는 조건이 왜 들어있는지는 잘 모르겠네요.