JS 탐욕(Greedy) 알고리즘 기초 12

✏️ 현재 상황에서 당장 가장 좋아보이는 상황만을 선택하는 알고리즘이다.

 

✏️ 동전0 https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

 

✏️ ATM https://www.acmicpc.net/problem/11399

11399번: ATM

 

✏️ 잃어버린 괄호 https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

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

let result = 0;
let minusGrp = input.split('-');
for(let i=0; i<minusGrp.length; i++){
    let plusSum = minusGrp[i].split('+').map(Number).reduce((a,b)=>a+b);
    if(i==0) result += plusSum;
    else result -= plusSum;
}

console.log(result);

---

✏️ 설탕 배달 https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin');
let result = 0;

while(input >= 0){
    if(input == 0 || input % 5 == 0){
        result += parseInt(input/5);
        input %= 5;
        break;
    }
    input -= 3;
    result +=1 ;
}

if(input<0) result=-1;

console.log(result);

처음에는 순서대로 5로 나눈 몫을 세고, 그 나머지 값으로 3으로 나눈 몫을 세고 3으로 나눈 나머지값이 0보다 클 경우 -1을 리턴하면 된다고 생각 했는데 그럼 input이 11일 경우 5로 나눈 나머지값이 1이기 때문에 3으로 나누지도 못하고 남은 값이 1이라 결국 -1이 리턴된다... 그래서 5로 나누어 떨어지는 경우가 될때까지 3을 우선적으로 빼줘야된다.

 

✏️ 💢헤맸으니 다시 풀어보자💢 A → B https://www.acmicpc.net/problem/16953

16953번: A → B

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');
let [a, b] = input[0].split(' ').map(Number);
let result = 1;
let flag = false;

while(a <= b){
    if (a==b){
        flag = true;
        break;
    }
    if(b%2 == 0) {
      b = parseInt(b/2);
    }
    else if (b%10 == 1) {
      b = parseInt(b/10);
    }
    else {
      break;
    }
    result ++;
}
if (flag) console.log(result);
else console.log(-1);

 

✏️ 수들의 합 https://www.acmicpc.net/problem/1789

1789번: 수들의 합

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');
let n = Number(input[0]);
let sum = 0;
let current = 0;

while(sum<=n){
    current ++;
    sum += current;
}

console.log(current-1);

 

✏️ 💢헤맸으니 다시 풀어보자💢 신입 사원 https://www.acmicpc.net/problem/1946

1946번: 신입 사원

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');
let testCase = Number(input[0]);
let startLine = 1;

for(let i=0; i<testCase; i++){
    let lineCnt = Number(input[startLine]);
    let arr = [];
    
    for(let j=startLine; j<=startLine+lineCnt; j++){
        let data = input[j].split(' ').map(Number);
        arr.push(data);
    }
    
    arr.sort((a,b) => a[0]-b[0]);
    let cnt = 0;
    let min = 10000000;
    for(let [x, y] of arr){
        if(y<min){
            min = y;
            cnt ++;

        }
    }
    
    console.log(cnt);
    startLine += lineCnt+1;
    
}