백준 - 보물(1026번)
문제
-
옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.
-
길이가 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의 최솟값을 출력한다.
이 문제에서 포인트는 하나의 배열을 오름차순, 다른 하나의 배열을 내림차순으로 정리한 후 각 인덱스의 배열끼리 곱해서 합하는 것이다.
코드 설계
문제 해결의 단계는 아래와 같다.
- 수의 갯수를
N으로 입력받는다. A배열과B배열의 값을 입력받는다.A배열을 오름차순으로,B배열을 내림차순으로 정렬한다.- 각 인덱스의 값끼리 곱하여 합한다.
제출한 답
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int asc(const int* a, const int* b) {
return *a - *b; // 오름차순
}
int dsc(const int* a, const int* b) {
return *b - *a; // 내림차순
}
int main() {
int N;
int A[50];
int B[50];
int S = 0;
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d", &A[i]);
}
for (int i = 0; i < N; i++) {
scanf("%d", &B[i]);
}
qsort(A, N, sizeof(int), asc);
qsort(B, N, sizeof(int), dsc);
for (int i = 0; i < N; i++) {
S += (A[i] * B[i]);
}
printf("%d", S);
}
qsort() 함수
이번 코드에서는 정렬함수를 사용해서 문제를 해결했다.
우선 qsort() 함수를 사용하기 위해서는 <stdlib.h>를 import 해와야한다.
첫 번째 인자로는 정렬할 배열의 시작 주소를 넘겨준다. 두 번째 인자로는 요소의 갯수를 넘겨준다. 세 번째 인자로는 요소의 크기를 넘겨준다. 마지막 인자에는 정렬 기준을 세우는 함수를 넘겨주어야한다.
정렬 기준 함수라는 것은 쉽게 말하면 반환값이 양수이면 두 수의 자리를 바꾸고 음수이면 자리를 바꾸지 않는다. 문제 해결에서 사용한 코드를 예시로 설명하겠다.
int asc(const int* a, const int* b) {
return *a - *b; // 오름차순
}오름차순의 경우 a-b의 값이 양수(a>b)이면 두 수의 자리를 바꾼다. a는 b보다 큰 수 이면서 먼저 오는 수이므로 이 수가 뒤로가게된다. 반대로 a-b의 값이 음수(a<b)이면 두 수의 자리를 바꾸지 않는다. 이때는 작은 수가 앞에 있도록 고정된다. 이 과정을 반복하면서 큰수가 뒤로가게 되므로 자연스럽게 오름차순 정렬이 된다.
int dsc(const int* a, const int* b) {
return *b - *a; // 내림차순
}내림차순의 경우 오름차순과 반대로 생각하여 뒷 순서인 b-a의 값을 구하는 코드로 수정하면 된다.
💡한줄평
C언어로 문제를 푸는 것은 백준에서 JS로 문제를 푸는 것이 복잡하거니와 순전히 시간복잡도를 고려하지 않고 싶어서였다.
그러나 이 문제를 풀면서 정렬함수의 오름차순, 내림차순을 구현하기 위해 기준이 되는 함수를 만들어야되는 것에 피로감을 느꼈다. 또한, 프론트엔드 개발자를 희망하는 사람으로서 JS를 놓을 수는 없다. 다음 문제는 JS로 풀이해야겠다..
