백준 12931 두 배 더하기

문제

두가지 연산만 실행해서 목표 배열을 만드는 그리디 문제이다. 배열에 있는 값을 뺀다는 조건이 없으므로 +만 되면 되기 때문에 역으로 뒤에서부터 2로 나누던가, 하나의 값을 1 빼던가 하는 방식을 선택해서 0으로만 되는 배열을 만드는 방식으로 했다.

그르디는 순서와 분기 처리, 조건을 제대로만 하면 금방 풀렸다.

1. 모든 값들을 2로 나눌 수 있으면 일단 나누고 본다
2. 2로 못나누면 못 나누는 원인의 값들에서 1을 뺀다 를 반복하면 된다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
 
const n = +inputs[0];
let targetArr = inputs[1].split(" ").map(Number);
 
let min = 0;
while (targetArr.some((a) => a > 0)) {
  if (targetArr.every((a) => a % 2 === 0)) {
    targetArr = targetArr.map((a) => a / 2);
    min++;
  } else {
    targetArr.forEach((a, i) => {
      if (a && a % 2 !== 0) {
        min++;
        targetArr[i]--;
      }
    });
  }
}
 
console.log(min);
 

나같은 경우는 다 잘 써놓고 while문의 조건을 targetArr.every(a => a)로 써놓고 아래에서 남은 값들을 더했는데 칼차단을 몇번 당하고 지피티가 알려줘서야 알았다… 조금이라도 값이 있다면 일단 2로 나눌 여지가 있으므로 루프에서 빠져나온 뒤에는 모든 배열이 0이 되도록 하는 것이 베스트이다.