백준 1026: 보물 - javascript (그리디)

문제 출처 

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

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의 최솟값을 출력한다.

예제 입력 1 복사

5
1 1 1 6 0
2 7 8 3 1

예제 출력 1 복사

18

예제 입력 2 복사

3
1 1 3
10 30 20

예제 출력 2 복사

80

예제 입력 3 복사

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

예제 출력 3 복사

528

 

문제 풀이 힌트 

: A배열의 작은 값 부터 , B배열의 큰 값부터 곱한 값들을 더한 것이 최솟 값이 된다. 

- A배열을 오름차순 정렬한다. 

- B배열은 정렬하지 말라고 했으니 가장 큰 값을 빼온다. 

 

정답 풀이 코드 

let input = require('fs').readFileSync('/dev/stdin').toString().split('\n'); 
const N = Number(input.shift());
const A = input[0].split(' ').map(Number); 
const B = input[1].split(' ').map(Number); 
function solution(N, A, B){
    let answer = 0;
    let sortedA = A.sort((a,b)=> a-b)
    for(let i=0; i<N; i++){
       let pickB = B.indexOf(Math.max(...B))
       answer += sortedA[i] * B[pickB]; 
        B.splice(pickB, 1);
    }
    return answer; 
    }
console.log(solution(N,A,B))

 

의사 코드 추가 

let input = require('fs').readFileSync('/dev/stdin').toString().split('\n'); 
const N = Number(input.shift());
const A = input[0].split(' ').map(Number); 
const B = input[1].split(' ').map(Number); 

function solution(N, A, B){
    let answer = 0;
    let sortedA = A.sort((a,b)=> a-b) //A 오름차순 정렬
    for(let i=0; i<N; i++){
       let pickB = B.indexOf(Math.max(...B)) //B의 가장 큰값의 idx 값을 구한다. 
       answer += sortedA[i] * B[pickB]; //A의 가장 작은 값부터 * B의 가장 큰 값부터 
        B.splice(pickB, 1); //B에서 가장 큰 값 삭제 
    }
    return answer; 
    }
    
console.log(solution(N,A,B))

 

알고가는 것 

reduce 함수의 3번째 인자로 idx 값이라는 것을 알고간다. !

function solution(N, A, B){
    let answer = 0;
    let sortedA = A.sort((a,b)=> a-b) //A정렬
    let sortedB = B.sort((a,b)=> b-a) //B정렬
    answer = sortedA.reduce((acc,cur,idx) => acc + cur * sortedB[idx],0)
    return answer; 
    }
console.log(solution(N,A,B))