[STUDY] 탐욕 알고리즘 문제풀이 2 230904

~57일차~

1. 설탕 배달

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

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

1) 현재 값이 5로 나누어 떨어지는 경우, 5로 나누면 될 것이다.
2) 그렇지 않다면, 기존의 값이 5로 나누어 떨어지는 값이 될 때까지 3을 빼준 뒤 1)을 수행한다.

제출 답안

미제출

-오답 !

• 총 kg인 n을 5로 나누고 그 다음 3을 나누는 식으로 하려 했지만 코드를 제대로 짜지 못했다.

정답 예시

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

let n = Number(input[0]);
let cnt = 0;
let flag = false;

while (n >= 0) {
  //n이 0이 되었거나, n로 나누어 떨어지는 값인 경우
  if ( n== 0 || n% 5 == 0) {
    cnt += parseInt(n/5);
    console.log(cnt);
    flag = true;
    break;
  }
  n -= 3;
  cnt += 1;
}
if (!flag) {
console.log(-1);
}

2. A -> B

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

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

• 값이 2로 나눠지는 경우 -> 2로 나누는 연산
• 그렇지 않고, 일의 자릿수가 1인 경우 -> 10으로 나누는 연산
• 위 모두 해당 X -> 이동 불가능, 종료

제출 답안

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

// 
let a = Number(input[0].split(' ')[0]);
let b = Number(input[0].split(' ')[1]);

let cnt = 0;

function count(b) {
  while (a = b) {
    if ( b% 2 == 0) {
      b /= 2;
      cnt++;
    } else {
    b = (b - 1)/10;
    cnt++;
    }
  }
  return a = b ? cnt : -1;
}

console.log(count(b));

-오답 : 시간초과
vs에서 예시 2개를 돌렸을 때는 정상적으로 나왔지만
나머지 예시 1개는 무한로딩, 백준에서는 시간초과가 나왔다.

정답 예시

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

let [a, b] = input[0].split(' ').map(Number);
let flag = false;
let result = 1;

while (a <= b) {
  if (a == b) {  //  a와 b가 같아질 때 탈출
    flag = true;
    break;
  }
  if (b%2 == 0) b = parseInt(b / 2); // 2로 나누어 떨어지는 경우
  else if (b % 10 == 1) b = parseInt(b/10); // 그렇지 않고, 일의 자리수가 1인 경우
  else break; // 위의 경우가 모두 해당되지 않는 경우
  result++;
}

if (flag) console.log(result);
else console.log(-1);

3. 수들의 합

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

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

• 가장 작은 수부터 더하기
  1부터 시작하여, 차례대로 더하면서, 합이 S를 넘지않도록한다.

제출 답안

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

// 
let s = Number(input[0]);

// 누적 시작
let cur = 0;
//총합
let sum = 0;

while ( sum <= s ) {
  cur += 1;
  sum += cur;
}
console.log(cur);

-오답 : 마지막에 -1을 하지 않았다.

정답 예시

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

let s = Number(input[0]);
let cur = 0;
let sum = 0;

while ( sum <= s ) {
  cur += 1;
  sum += cur;
}
console.log(cur-1);

4. 신입 사원

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

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

• 오름차순을 사용, 특정 지원자보다 두 시험 성적이 모두 높은 지원자가 있는지만 확인

제출 답안

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

let testCase = Number(input[0]); //테스트케이스 개수
let n = Number(input[1]); // 지원자수
let arr = [];
for(let i = 2; i <=n; i++) {
  let [x, y] =  input[i].split(' ').map(Number);
  arr.push([x,y]);
}

arr.sort((a,b) => a[0] - b[0]); // 서류심사 성적순

let select = arr[0][1]; //비교 기준
let cnt = 0;
// 면접시험 비교
for (let j=1; j<arr.length; j++) {
  if (select >arr[j][1]) {
  select = arr[j][1];
  cnt += 1;
  }
}

console.log(cnt);

-오답 : 테스트케이스를 다루지 못했다.

정답 예시

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

let testCase = Number(input[0]); 
let line = 1;
for(let tc = 0; tc <testCase; tc++) {
  let n = Number(input[line]);
  let arr = [];
  for (let i = line + 1; i <=line +n; i++) {
    let data =  input[i].split(' ').map(Number);
    arr.push(data);
    }
arr.sort((x,y) => x[0] - y[0]);
let count = 0;
let minValue = 100001;
for (let [x,y] of arr) {
  if (y < minValue) {
    minValue = y;
    count += 1;
  }
}
console.log(count);
line += n + 1;
}

• 사실 이 문제는 문제에 대한 이해도가 떨어져서 나중에 다시 풀어볼 예정이다.