그리디 문제풀이(2)

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

2839번: 설탕 배달

 

[나의 오답 코드]

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

let answer=Number(input[0]) // 초기값 , 18
let flag = false // 초기값 false

while(answer>=0){ answer가 0 이상일 때는 계속해서 실행
  if(answer%5===0){ answer 가 5로 나누어 떨어지니?
    answer = parseInt(answer/5)  answer = answer를 5로 나눈 몫
    flag=true // flag =true
    break; // 실행 멈춤
  }else{
   answer=answer-3 // 나눠 떨어지지 않으면 계속해서 3을 빼줌
  }
}

if(flag===true){
// flag===true? 5가 하나이상이다 => 원래의 answer에는 5가 몇번 들어 있는지가 할당되어져 있음
// 초기값 Number(input[0])에서 5가 차지하는 비중만큼(answer*5)을 빼준값을 3으로 나눈 몫만큼 더해줌
  answer = answer +  parseInt((Number(input[0])-answer*5)/3)
}else if(input%3===0){
//flag가 true가 아니지만 3의 배수로는 이루어져 있는 경우(3,6,9...)의 경우에는 처음값을 3으로 나는 몫
answer=parseInt(input/3)
}
else{
//3으로도 5로도 만들수 없는 경우에는 -1
  answer = -1
}

console.log(answer)

 

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

16953번: A → B

[나의 오답 코드]

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let [n,k]=input[0].split(" ").map(Number)
let answer=0;
let flag=false
while(n<=k){
  if(k===n){
    flag=true
    answer++
    console.log(answer)
    break
  }
  else if(k%2===0){
    k=parseInt(k/2)
    answer++
  }else{
    k=parseInt(k/10)
    answer++
  }
}

if(!flag) console.log(-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){
        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("index.txt").toString().split("\n");
let n= Number(input[0])
let a = 1
let b = 1
let c= -2*n
let answer= (-b+Math.sqrt(Math.pow(b,2)-4*a*c))/2*a
console.log(Math.floor(answer))

이차방정식 근의 공식을 자바스크립트로 활용하여 문제를 풀었다. 참고한 자료는 https://m.blog.naver.com/lee627498/220981699068

자바스크립트(javascript) - 2차방정식의 근 구하기

n이 1과 3사이의 값일 때는 1, 3과 6 사이의 값일때는 2, 6과 10 사이의 값일 때는 3 이런식으로 x(x-1)/2<=n<x(x+1)/2 일 때를 만족하는 x의 값이 정답이 되게 된다. 

 

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

1946번: 신입 사원

[풀이 방향]

(1) 순위 x를 기준으로 오름차순 정렬을 수행한다.

(2) 차례대로 한 명씩 확인하며, 순위 y가 현재까지 확인했던 y 중에서 가장 작은 수라면 카운트 한다.

let fs =require('fs');
let input = fs.readFileSync('input.txt').toString().split('\n');

let testCase = Number(input[0]); // 테스트 케이스의 개수
let line=1;

for(let tc=0;tc<testCase;tc++){
  n=Number(input[line]);
  //line=1, 7 => n=5,7
  let arr=[];
  for(let i=line+1;i<=line+n;i++){
    let data=input[i].split(" ").map(Number);
    arr.push(data);
  }
//첫번쨰 테스트 케이스 [[3,2],[1,4],[4,1],[2,3],[5,5]]
//두번째 테스트 케이스 [[3,6],[7,3],[4,2],[1,4],[5,7],[2,5],[6,1]]
arr.sort((x,y)=>x[0]-y[0]) // x 순위를 기준으로 오름차수 정렬
//첫번쨰 테스트 케이스 [[1,4],[2,3],[3,2],[4,1],[5,5]]
//두번째 테스트 케이스 [[1,4],[2,5],[3,6],[4,2],[5,7],[6,1],[7,3]]
let count=0;
let minValue= Number.MAX_SAFE_INTEGER;
for(let [x,y] of arr){
  if(y<minValue){
    minValue=y;
    count+=1;
  }
}
  console.log(count);
  line=line+n+1 // 다음번쨰 테스트 케이스의 라인
}

정답 코드 자체는 간단한데, 문제는 이게 어떻게 정답을 확보하는지 이해가 잘되지 않는다. x를 기준으로 오름차순을 한 뒤 y가 y의 최솟값이기만 하면 추가해나가는 방식이 가장 신입사원을 많이 뽑을 수 있는 방법인지는 잘 이해가 되지 않는다. 나중에 다시 풀어보는 것으로...