[백준 2437번] 그리디 알고리즘 - 저울

✨ 문제 ✨

✨ 정답 ✨

const { count } = require("console");
const fs = require("fs");
const { nextTick } = require("process");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./예제.txt";
let input = fs.readFileSync(filePath).toString().trim();


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

input = input.split('\n')

const N=+input[0]
let array=input[1].slice().split(' ').map((el)=>+el).sort((a,b)=>a-b)

let answer=1;
for(let i=0;i<array.length;i++){
  if (answer<array[i]){
    break;
  }
  answer+=array[i];
}

🧵 참고한 정답지 🧵

https://kimbangg.tistory.com/189

💡💡 기억해야 할 점 💡💡

1~n-1번째 추의 합 <n번째 추의 무게일 때가 답인 건 알았는데 어떻게 정리를 해서 구현해야 하는지는 몰랐다.
아니 말을 정리해서 쓰고 나니까 이걸 왜 못 풀었나 싶긴 하다.
n은 항상 큰 수라 생각해서 n에 이르기까지 고려해야 할 케이스가 굉장히 많을 것이라는 이상한 불안감이 들어서인듯하다. 답지에서 본 1,3,9의 간단한 예제를 보니 이해하기 쉬웠다.

• 고민 결과 1~n-1번째 추의 합<n번째 추의 무게라는 사실을 의심한 이유는 다음 사진과 같다.(쓰면서 난 바보라는 생각이 확고해졌다.)
  
  마지막 줄이 n-1째 추까지 사용하여 만들 수 있는 무게들을 나열한 것이다. n-1번째 추까지 이용하여 만들 수 있는 최댓값은 20이다. 여기서 나는 21을 만들기 위해 필요한 숫자가 n보다 작아도 가능하다는 사실에 집중했다. 백준의 예제에서는 8 하나만 더 있어도 답이 21이 아닌 29가 된다. 왜 쓸데없는 것에 꽂혀서 문제를 못 푼건지 이해가 안 간다. 8~20까지 다 되는데. 쓰면서도 내 자신이 이해가 안 간다. 아니 거의 다 왔는데 왜 못 풀었을까. 낫 놓고 기역자도 모른다는 이럴 때 쓰는 말인 것 같다.