그리디 문제풀이(3)

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

13305번: 주유소

let fs = require("fs");
let input = fs.readFileSync("input.txt").toString().split("\n");
let distanceArray = input[1].split(" ").map(Number)
let costArray=input[2].split(" ").map(Number)
costArray.pop()// 맨마지막은 필요없음 => 맨마지막 도시 전에 기름이 필요하기 때문
let totalCost=0

for(i=0;i<distanceArray.length;i++){
    if(Math.min(...costArray)!==costArray[i]){//도시의 주유값이 최소 비용이 아닌 경우
      totalCost=totalCost+costArray[i]*distanceArray[i] // 딱 해당도시를 가는데 필요한 만큼만 넣음
      distanceArray[i]=0 // 남은 가야할 거리에서 빼주기 위해서 0 할당
      costArray[i]=Number.MAX_SAFE_INTEGER // 최솟값에 영향을 미치지 않게 하기 위해서 큰 값 할당
    }else{
      let leftDistance=distanceArray.reduce((a,b)=>a+b) // 남은 총 가야할 거리
      totalCost=totalCost+leftDistance*Math.min(...costArray)// 현재에서 최솟값을 곱해줌
      break// 실행 멈춤
    }

}

console.log(totalCost)

 

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

1931번: 회의실 배정

[풀이 방향]

• 가장 먼저 모든 회의에 대하여 오름차순을 정렬한다.
• 정렬할 때는 (1) 종료 시점 (2) 시작 시점을 우선순위로 한다.
• 첫번째 회의부터 시작해 겹치지 않게 최대한 많은 회의를 선택한다.
• 종료시점이 이른 회의부터 확인하며, 겹치지 않게 배정한다. 

[정답 코드]

let fs =require('fs');
let input = fs.readFileSync('input.txt').toString().split('\n');
let n = Number(input[0]) // 회의의 개수
let arr = [] // 각 회의에 대한 (시작 시점, 종료 시점) 입력받기
for(i=1;i<=n;i++) arr.push(input[i].split(" ").map(Number))

arr.sort(function(a,b){
  if(a[1]!=b[1]) return a[1]-b[1] // 우선적으로 종료 시점 기준으로 오름차순
  else return a[0]-b[0]// 그다음으로는 시작 시점 기준으로 오름차순
})
console.log(arr)
//[[1,4],[3,5],[0,6],[5,7],[3,8],[5,9],[6,10],[8,11],[8,12],[2,13],[12,14]]


let cnt =1;
let cur =0;

for(j=1;j<n;j++){
  if(arr[cur][1]<=arr[j][0]){//현재의 종료시점 이후에 다음의 시작시점이 올 때
    cur = j;
    cnt=cnt+1
    
  }
}
//[1,4],[5,7],[8,11],[12,14]
console.log(cnt)

이번에도 풀이 자체는 간단하지만 어떻게 종료시점을 기준으로 오름차순을 한다 <= 라는 아이디어를 떠올릴 수 있는지가 가장 어려운 부분이었던것 같다.

 

 

 

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

11509번: 풍선 맞추기

[나의 오답코드]

let fs = require("fs");
let input = fs.readFileSync("input.txt").toString().split("\n");
let array = input[1].split(" ").map(Number);
let answer = 0;
for (let i = 0; i < array.length; i++) {
  if (!array.slice(i,array.length).includes(array[i] - 1)) {
    answer++;
  }
}
console.log(answer)

메모리 초과가 뜸...

[풀이 방향]

• 왼쪽부터 하나씩 풍선을 확인한다.
• 해당 높이에 존재하는 존재하는 화살이 없다면 화살을 새롭게 사용한다.

[정답코드]

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

let input = [];
rl.on('line',function(line){
  input.push(line)// 콘솔 입력 창에서 줄바꿈(Enter) 입력시마다 호출
}).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]=arrow[x]-1;
      arrow[x-1]=arrow[x-1]+1
    }else{
      arrow[x-1]=arrow[x-1]+1
      result=result+1 //화살 쏘기
    }
  }
  console.log(result);
  process.exit()
})

... 다음에 이해해보기로...

 

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

9009번: 피보나치

[풀이 방향]

• 피보나치 수 : 0,1,1,2,3,45,8,13,21,34,44,89...
• 명제: 양의 정수는 하나 혹은 그 이상의 서로 다른 피보나치 수들의 합으로 나타낼 수 있다.
• 가장 큰 피보나치 수부터 빼 나갈 때 최소 개수를 만족할 수 있다.
• X-A는 A보다 작은 서로 다른 피보나치 수들의 합으로 표현 가능하다.
• A는 가능한 가장 큰 피보나치 수를 의미한다.

 

[정답 코드]

let fs = require('fs');
let input = fs.readFileSync('input.txt').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 testCase = Number(input[0])

for(let tc = 1; tc<=testCase ;tc++){
  let n = Number(input[tc]);
  let result = [];
  let i = pibo.length-1 // 가장 큰 피보나치 수의 인덱스
  while(n>0){//n이 0이 될 때 까지
    if(n>=pibo[i]){//가능한 큰 피보나치 수부터 빼기
      n=n-pibo[i]
      result.push(pibo[i])
    }
    i--
  }
  let answer='';
  for(i=result.length-1;i>=0;i--) answer= answer+result[i]+' '// 오른차순 출력
  console.log(answer)
}

문제를 해결해나가는 아이디어 자체는 어렵지 않았으나 대체 피보나치 수열을 어떻게 처리하지? 에 대한 의문이 많았던 문제이다. 설마 어느정도 큰 수 까지 다 배열로 메모리에 저장을 해 두는 방식일지는 상상하지 못했다. 피보나치 수열이 기하 급수적으로 숫자가 커지는 성질 때문에 가능한 풀이 방법이었다고 생각한다.