[CS & Algorithm] 그리디 (greedy) 알고리즘 문제 풀이 (2)

1. 주유소 (13305)

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

A도시에서 N도시로 이동하는데 여러 도시를 거쳐 간다. 거리와 주유소의 비용이 각 도시마다 다른데 최소 비용으로 N도시에 도착하면 되는 문제다.

해결 방법

• 첫 도시에서는 다음 도시에 갈 때까지 주유를 무조건 해야한다. 때문에 minCost를 cost[0]로 설정하고 다음 도시까지 가는 cityLeng[0]만큼 주유한다.
• 다음 도시에서 부턴 minCost와 현재 인덱스의 cost를 비교하여 cityLeng만큼 주유한다.

let fs = require('fs')
let input = fs.readFileSync('/dev/stdin').toString().split('\n');

let n = Number(input[0])
let cityLeng = input[1].split(' ').map(Number);
let cost = input[2].split(' ').map(Number);
let minCost = cost[0];

let i = 0;
let j = BigInt(0);
while (i < n - 1)
{
  if (minCost > cost[i])
    minCost = cost[i];
  j += BigInt(minCost) * BigInt(cityLeng[i]);
  i++;
}
console.log(String(j));

---

2. 회의실 배정 (1931)

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

let fs = require('fs')
let input = fs.readFileSync('/dev/stdin').toString().split('\n');

let n = Number(input[0])
let arr = [];
for (let i = 1; i <= n; i++){
  let data = input[i].split(' ').map(Number)
  arr.push(data)
}

arr.sort((a,b)=> {
  if (a[1] != b[1]) return (a[1] - b[1]);
  else return (a[0] - b[0]);
})

let cur = 0;
let cnt = 1;
for (let i = 1; i < n; i++)
{
  if (arr[cur][1] <= arr[i][0]){
    cur = i;
    cnt += 1;
  }
}
console.log(cnt)

---

3. 풍선 맞추기 (11509)

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

const rl = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});

let input = [];
rl.on('line', function(line) {
  input.push(line);
}).on('close', function(){
  let data = input[1].split(' ').map(Number);
  let result = 0;
  let arrow = new Array(1000001).fill(0);
  for (let x of data){
    if (arrow[x] > 0) {
      arrow[x] -= 1;
      arrow[x - 1] += 1;
    }
    else {
      arrow[x - 1] += 1;
      result += 1;
    }
  }
  console.log(result)
  process.exit();
})

---

4. 피보나치 (9009)

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

let fs = require('fs')
let input = fs.readFileSync('/dev/stdin').toString().split('\n');

pibo = []
pibo.push(0)
pibo.push(1)
while (pibo[pibo.length - 1] < 1e9) pibo.push(pibo[pibo.length-2] + pibo[pibo.length-1]);

let tc = Number(input[0]);

for (let i = 1; i <= tc; i++)
  {
    let arr = [];
    let j = pibo.length - 1;
    let now = Number(input[i]);
    while (now > 0){
      if (now >= pibo[j]){
        now -= pibo[j];
        arr.push(pibo[j]);
      }
      j--;
    }
    let res = '';
    for (let i = arr.length - 1; i >= 0; i--) res += arr[i] + ' ';
    console.log(res);
  }