[백준/node.js] 1026번 보물

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

1026번: 보물

 

• 사용언어 : node.js
• 알고리즘 : 수학, 그리디 알고리즘, 정렬
• Solved.ac Tier : SILVER IV

 

 

 

node.js 코드

1. 문제 정리

국왕 김지민씨가 문제를 냈다고 한다. 길이가 N인 정수 배열 A와 B가 있다. 함수 S는 S = A[0] × B[0] + ... + A[N-1] × B[N-1]라고 한다.

S의 값을 가장 적게 만들어 달라고 부탁한다. (A를 재배열 함으로서)

ex)

5
1 1 1 6 0
2 7 8 3 1

5
1 1 0 1 6
2 7 8 3 1
2 7 0 3 6 = 18

그리 하여 내 나름대로 A배열만 재 배열 되어 문제가 풀릴 수 있도록 만들어 보았다.

const fs = require('fs');
let [num, ...inputs] = fs.readFileSync("/dev/stdin").toString().trim().split('\n');
let countArr = Array.from({length:num}, ()=>1);
let firstArr = inputs[0].split(' ').map((e)=>parseInt(e))
let secondArr = inputs[1].split(' ').map((e)=>parseInt(e))

for(let i = 0; i < num; i++){
    for(let j = 0; j < num; j++){
        if(secondArr[i] < secondArr[j]){
            countArr[i]++
        }
    }
}

firstArr.sort((a,b)=>a-b)
let sum = 0;
for(let i = 0; i < num; i++){
    sum += firstArr[countArr[i] - 1] * secondArr[i];
}

console.log(sum)

countArr이라는 배열을 만들어 secondArr의 배열 크기 값을 가져오도록 했다. 쉽게 말해 순위를 매겼다.

2 7 8 3 1
4 2 1 3 5

이렇게 해서 firstArr[countArr[i]] * secondArr[i] 값을 더 해주었다.

하지만 실패더라.. ;; 이유는 몰?루

그래서 결국 B 배열도 건들여서 문제를 해결 했다.

firstArr은 오름차순으로 정렬 secondArr은 내림차순으로 정렬 해주고 

firstArr[i] * secondArr[i]의 값을 sum에 더해주니깐 정답 처리 되었다.

 

2. 완성 코드

const fs = require('fs');
let [num, ...inputs] = fs.readFileSync("/dev/stdin").toString().trim().split('\n');
let countArr = Array.from({length:num}, ()=>1);
let firstArr = inputs[0].split(' ').map((e)=>parseInt(e))
let secondArr = inputs[1].split(' ').map((e)=>parseInt(e))

firstArr.sort((a,b)=>a-b)
secondArr.sort((a,b)=>b-a)

let sum = 0;
for(let i = 0; i < num; i++){
    sum += firstArr[i] * secondArr[i];
}

console.log(sum)