[STUDY] 탐욕 알고리즘 문제풀이 3 230905

~58일차~

1. 주유소

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

강의에서 제시한 문제 해결 아이디어

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

제출 답안

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

let city = Number(input[0]);
let dArray = input[1].split(' ').map(Number); //거리
let pArray = input[2].split(' ').map(Number); //비용

let lowest = pArray[0]; //최저가

let total = pArray[0] * dArray[0]; //초기값 설정

for (let i = 1; i<dArray.length -1; i++) {
  if (lowest >= pArray[i]) { //최저가 비교
      lowest = pArray[i];
      for (let j = 1; j<dArray.length; j++) {
        //최저가를 거리에 곱해서 총 가격(total)에 더하기
        total += lowest * dArray[j]
      }
  }
}

console.log(total);

-오답 !
vs에서는 예시 3개가 모두 정상출력되었는데 백준에서는 틀렸다고 나온다.

정답 예시

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

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

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

//도로당 이동 비용의 합 계산
let answer = BigInt(0);
for (let i = 0; i < n-1; i++) {
  //JS에서 큰 정수 처리할때 BigInt 사용
  answer += BigInt(dist[i]) * BigInt(cost[i]);
}
console.log(String(answer)); // 뒤에 붙는 'n'제거

2. 회의실 배정

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

강의에서 제시한 문제 해결 아이디어

• 모든 회의에 대하여 오름차순 정렬
• 정렬 시 1. 종료시점 2. 시작 시점을 우선순위로 함
• 종료 시점이 이른 회의부터 확인

제출 답안

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 start = Number(input[i].split(' ')[0]);
  let end = Number(input[i].split(' ')[1]);
  arr.push([start, end]);
}

// 시작시간 오름차순 정렬
arr.sort((a,b) => a[0] - b[0]);

let cnt= 0;
let first = arr[0][0];
for (let i = 1; i<n; i++) {
  if(first = arr[i][0]){  // 시작시간이 같은 회의 수대로 count 시도
    first = arr[i][0];
    cnt += 1;
  }
}

console.log(cnt);

-오답 : first = arr[i][0] 이부분에 대해 판별이 되지 않고 모든 수를 count 했다.

정답 예시

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++) arr.push(input[i].split(' ').map(Number));

// 1.종료시점, 시작시점을 우선순위로 오름차순 정렬
arr.sort(function(a,b) {
  if(a[1] != b[1]) return a[1] - b[1];
  else return  a[0] - b[0]; //종료시점 같으면 시작순으로 정렬
});
let cnt= 1, cur = 0;
for (let i = 1; i<n; i++) {
  if(arr[cur][1] <= arr[i][0]){  //현재 회의 종료 후 시작되는 경우 카운트
    cur = i;
    cnt += 1;
  }
}
console.log(cnt);

3. 풍선 맞추기

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

강의에서 제시한 문제 해결 아이디어

제출 답안

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

//풍선 개수
let n = Number(input[0]);
//풍선 높이
let arr = input[1].split(' ').map(Number);

let cnt= 1;
let height = arr[0];
for (let i = 1; i<n; i++) {
  if((height - arr[i]) < 1) {
    height = arr[i];
    cnt += 1;
  }
  else height = arr[i];
}

console.log(cnt); 

-오답 : vs에서 출력값은 똑같이 나왔지만, 백준에서 오답
그리고, 문제의 이해부터가 잘못되었다.
왼쪽에서부터 순서대로 시작해서 낮은 높이면 맞추고 아니면 화살을 추가한다고 생각했다.

정답 예시

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. 피보나치

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 testCases = Number(input[0]);
//데이터
for(let tc = 1; tc <= testCases; tc++) {
  let n = Number(input[tc]);
  let result = [];
  let i = pibo.length -1 // 가장 큰 피보나치 수의 인덱스
  while (n>0) { // 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); 
}

강의가 진행될 수록 문제 이해 자체가 어려워지면서 시간이 많이 소요되거나 방향성을 잡기가 어려워졌다. 코테 강의 한바퀴 돌고 난 후에 다시 복습을 하려 한다.