그리디 문제풀이(3)

8. 주유소(13305)

문제

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다.

제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 3리터의 기름을 넣고(3×2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1×4 = 4원) 제일 오른쪽 도시로 이동하면, 총 비용은 20원이다. 또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 4리터의 기름을 넣고(4×2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다.

출력

표준 출력으로 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 출력한다.

작성한 코드

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

let n = Number(input[0]); // 도시의 개수(2 <= n <= 1,000)
let distance = input[1].split(" ").map(Number); // 도시 간 거리
let oilLiter = input[2].split(" ").map(Number); // 도시 별 리터 당 기름 가격

// 주유 비용(oilLiter) 배열의 값을 비오름차순이 되도록 변환
// [5, 2, 4, 1] -> [5, 2, 2, 1]
let minCost = oilLiter[0];
for (let i = 0; i < n; i++) {
  minCost = Math.min(minCost, oilLiter[i]);
  oilLiter[i] = minCost;
}

// 도로당 이동 비용의 합 계산
let answer = BigInt(0);
for (let i = 0; i < n - 1; i++) {
  // JS에서 큰 정수 처리할 때 BigInt 사용
  answer += BigInt(distance[i]) * BigInt(oilLiter[i]);
}

console.log(String(answer)); // 뒤에 붙는 'n' 제거

풀이

• 처음에 생각한 풀이

  • 현재 있는 곳의 기름 값이 다음 장소의 기름 값보다 클 경우 최소한만 넣기

  • 만약 같거나 클 경우 다 넣기

    → 이럴 경우, 중간에 더 작은 기름 값이 나와도 적용이 안되는 문제 발생..ㅠ

• 주유 비용을 비오름차순으로 변경
  • 자기보다 뒤에 있는 비싼 주유소에 대해서는 미리 결제

배운 점

BigInt: Number 원시 값이 안정적으로 나타낼 수 있는 최대치인 $2^{53}-1$ (9007199254740991 ~ -9007199254740991)보다 큰 정수 표현할 수 있는 내장 객체

• 정수 리터럴 뒤에 n을 붙이거나(10n), 함수 BigInt() 호출하여 생성

  const biggestInt = 9007199254740991n;
  const hugeString = BigInt("9007199254740991");-

• 연산자는 +, -, *, **, %, /사용 가능
  • / 연산자는 소수점 이하를 버림
  • Number와 혼합하여 사용 X
• BigInt와 Number는 일치하지 않지만 동등함

  0n === 0; // false
  0n == 0; // true

• 정렬 방법

  array.sort((a,b) => (a < b ? -1 : 1));
  
  const mixed = [4n, 6, -12n, 10, 4, 0, 0n];
  mixed.sort();
  // [-12n, 0, 0n, 10, 4n, 4, 6]

• 내장 Math 객체 메서드와 함께 사용될 수 X

BigInt - JavaScript | MDN

---

9. 회의실 배정(1931)

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

작성한 코드

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

let n = Number(input[0]); // 회의의 수

// 각 회의 정보([시작시간, 끝나는 시간])
let meetings = [];
for (let i = 1; i <= n; i++) {
  let meeting = input[i].split(" ").map(Number);
  meetings.push(meeting);
}

// (1) 종료 시점 (2) 시작 시점을 우선순위로 오름차순 정렬
meetings.sort((a, b) => a[1] - b[1] || a[0] - b[0]);

let cnt = 1;
let cur = 0; // 첫 번째 회의부터 확인

for (let i = 1; i < n; i++) {
  // 현재 회의가 끝난 이후에 회의가 시작되는 경우 카운트
  if (meetings[cur][1] <= meetings[i][0]) {
    cur = i;
    cnt += 1;
  }
}

console.log(cnt);

풀이

• 각 회의가 겹치지 않게 하면서 회의실 사용할 수 있는 회의의 최대 개수 계산

  • 가장 먼저 모든 회의에 대하여 오름차순 정렬

  • 정렬할 때 1) 종료 시점 2) 시작 시점을 우선순위로 하기

  • 첫 번째 회의부터 시작해 겹치지 않게 최대한 많은 회의 선택

    → 종료 시점이 이른 회의부터 확인!

---

10. 풍선 맞추기(11509)

문제

큰 방에 N개의 풍선이 떠있다. 풍선들은 왼쪽부터 오른쪽까지 일렬로 있다. 진솔이는 화살 가지고 노는 것과 사냥 연습하는 것을 좋아한다. 진솔이는 화살을 왼쪽에서 오른쪽으로 쏜다. 높이는 임의로 선택한다. 화살은 선택된 높이 H에서 풍선을 마주칠 때까지 왼쪽에서 오른쪽으로 이동한다. 화살이 풍선을 마주치는 순간, 풍선은 터지고 사라진다. 화살은 계속해서 가던길을 가는데 높이는 1 줄어든다. 그러므로 만약 화살이 높이 H에서 이동 중이었다면 풍선을 터트린 후에는 높이가 H-1이 된다.

우리의 목표는 모든 풍선을 터트리되 가능한한 적은 화살을 사용하는 것이다.

입력

첫 번째 줄에는 정수 N(1 ≤ N ≤ 1 000 000)이 들어온다.

두 번째 줄에는 배열 Hi가 N개 들어온다.

각각의 Hi(1 ≤ Hi ≤ 1 000 000)는 i번째 풍선의 높이에 해당하며 왼쪽에서 오른쪽으로 나열되는 순서이다.

출력

첫 번째 줄 한줄에 최소한 필요한 화살의 개수를 출력한다.

내가 작성한 코드 → 시간 초과

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

let n = Number(input[0]); // 풍선의 개수
let hList = input[1].split(" ").map(Number); // 풍선의 높이
// 나머지 풍선 중 자기 보다 1작은 수가 있는지 확인

let arrowCnt = 0; // 화살 수
while (hList.length > 0) {
  arrowCnt += 1;
  let h = hList[0];
  hList.splice(0, 1);
  while (hList.includes(h - 1)) {
    let idx = hList.indexOf(h - 1);
    h = hList[idx];
    hList.splice(idx, 1);
  }
}
console.log(arrowCnt);

풀이

• 맞춘 풍선 제거하면서 나머지 풍선 중 1차이 나는 풍선이 있는지 확인하며 제거
• 시간 초과..ㅠㅠ

올바른 코드

const rl = require("readline").createInterface({
  input: process.stdin,
  ouput: 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();
});

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

let n = Number(input[0]); // 풍선 개수
let hList = input[1].split(" ").map(Number);

let array = Array.from({ length: n + 1 }).fill(0);

let result = 0;
for (let i = 0; i < n; i++) {
  if (array[hList[i]] > 0) {
    array[hList[i]] -= 1;
    array[hList[i] - 1] += 1;
  } else {
    result += 1; // 화살
    array[hList[i] - 1] += 1;
  }
}

console.log(result);

풀이

• 왼쪽부터 하나씩 풍선 확인
• 해당 높이에 존재하는 화살이 없다면 화살을 새롭게 사용
  • [2, 1, 5, 4, 3]인 경우
    

---

11. 피보나치(9009)

문제

피보나치 수 ƒK는 ƒK = ƒK-1 + ƒK-2로 정의되며 초기값은 ƒ0 = 0과 ƒ1 = 1 이다. 양의 정수는 하나 혹은 그 이상의 서로 다른 피보나치 수들의 합으로 나타낼 수 있다는 사실은 잘 알려져 있다.

하나의 양의 정수에 대한 피보나치 수들의 합은 여러 가지 형태가 있다. 예를 들어 정수 100은 ƒ4 + ƒ6 + ƒ11 = 3 + 8 + 89 또는 ƒ1 + ƒ3 + ƒ6 + ƒ11 = 1 + 2 + 8 + 89, 또는 ƒ4 + ƒ6 + ƒ9 + ƒ10 = 3 + 8 + 34 + 55 등으로 나타낼 수 있다. 이 문제는 하나의 양의 정수를 최소 개수의 서로 다른 피보나치 수들의 합으로 나타내는 것이다.

하나의 양의 정수가 주어질 때, 피보나치 수들의 합이 주어진 정수와 같게 되는 최소 개수의 서로 다른 피보나치 수들을 구하라.

입력

입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T 가 주어진다. 각 테스트 데이터에는 하나의 정수 n이 주어진다. 단, 1 ≤ n ≤ 1,000,000,000.

출력

출력은 표준출력을 사용한다. 하나의 테스트 데이터에 대한 해를 하나의 줄에 출력한다. 각 테스트 데이터에 대해, 피보나치 수들의 합이 주어진 정수에 대해 같게 되는 최소수의 피보나치 수들을 증가하는 순서로 출력한다.

작성한 코드

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 testCases = Number(input[0]);
for (let tc = 1; tc <= testCases; tc++) {
  let n = Number(input[tc]);
  let result = [];
  let i = pibo.length - 1; // 가장 큰 피보나치 수의 인덱스
  // n이 0이 될 때까지
  while (n > 0) {
    // 가능한 큰 피보나치 수 부터 빼기
    if (n >= pibo[i]) {
      n -= pibo[i];
      result.push(pibo[i]);
    }
    i--;
  }
  let answer = "";
  for (let i = result.length - 1; i >= 0; i--) answer += result[i] + " "; // 오름차순 정렬
  console.log(answer);
}

풀이

• 가능한 가장 큰 피보나치 수부터 빼 나갈 때 최소 개수 만족
  • X-A는 A보다 작은 서로 다른 피보나치 수들의 합으로 표현 가능
  • A는 가능한 가장 큰 피보나치 수