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

1. 설탕 배달 (2839)

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

5kg, 3kg 봉지가 있고 최소 개수의 봉지를 가지고 (N)kg을 정확히 배달해야한다. 정확한 배달이 불가능하다면 -1 출력

• 5kg 봉지에 담는게 가장 좋은 전략이기 때문에 5로 나뉠 때까지 -3 을 하고 5로 나뉜다면 5로 나눈 횟수를 더하고 아니라면 -1을 출력한다.

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

let n = Number(input[0]);

let res = 0;

while (true)
  {
    if (n % 5 === 0 || n < 0)
      break;
    n -= 3;
    res++;
  }
if (n === 0)
  console.log(res)
else if ( n < 0)
  console.log(-1)
else
{
  res += parseInt(n / 5)
  console.log(res)
}

---

2. A -> B (16953)

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

A에서 B로 숫자를 바꾸고 싶을 때 할 수 있는 방법 2가지가 주어진다.
1. 2를 곱한다.
2. 1을 수 가장 오른쪽에 추가한다.

• 이 때 B에서 A로 도달하며 2로 나눈 나머지가 0이라면 2로 나눈다.
• 1의 자리 수가 1이라면 B에 1을 빼주고 10을 나눈다.
• 두 방법 전부 해당하지 않는다면, -1을 출력한다.

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

let [n, m] = [Number(input[0].split(' ')[0]), Number(input[0].split(' ')[1])];

let res = 1;

while (true)
  {
    if (m <= n)
      break;
    if (m % 2 === 0)
    {
      m /= 2;
      res++;
    }
    else if (m % 10 === 1)
    {
      m -= 1;
      m /= 10;
      res++;
    }
    else
      break;
  }
if (n === m)
  console.log(res)
else
  console.log(-1)

---

3. 수들의 합 (1789)

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

• 입력된 숫자를 각각 다른 자연수의 합으로 만들 때 최대 자연수의 갯수를 구하는 문제이다.

해결 방법

• 단순히 1부터 시작하며 N에 도달할 때까지 1씩 증가시키며 더한다. n을 넘어가게 되는 순간이 정답이다. (이미 더했던 숫자를 더 큰 값으로 변경했다고 가정하면 되기 때문에)

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

let n = Number(input[0].split(' ')[0])

let i = 0;
let j = 0;
while (i <= n)
  {
    j++;
    i += j;
  }
console.log(j - 1);

---

4. 신입 사원 (1946)

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

• 지원자가 갖는 두 가지 점수 중 하나라도 다른 지원자보다 떨어지지 않는 자를 찾는 문제이다.

해결 방법

• 지원자가 가진 두 가지 점수 중 앞에 오는 점수를 기준으로 오름차순 정렬을 한다.
• 그렇다면 첫 번째 정렬된 지원자 A는 무조건 합격이다.
• 두 번째 정렬된 지원자 B는 두 번째 점수가 A보다 높다면 합격이다.
• 세 번째 정렬된 지원자 C는 두 번째 점수가 A,B보다 높다면 합격이다... 이런 방식으로 minValue를 두 번째 점수의 비교 변수로 사용하며 비교해주면 된다.

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

let n = Number(input[0])

let i = 1
let j
for (let tc = 0; tc < n; tc++)
  {
    j = Number(input[i]) 
    let arr = [];
    for (let k = i + 1; k <= i + j; k++)
      {
        let cases = input[k].split(' ').map(Number)
        arr.push(cases)
      }
    i += j + 1;
    arr.sort((a, b)=>a[0]-b[0])
    let cnt = 0;
    let minValue = 100001;
    for(let [x, y] of arr)
      {
        if (y < minValue){
          minValue = y;
          cnt++;
        }
      }
    console.log(cnt);
  }