[백준 알고리즘] Node.js 15671. Lemonade Line

1. 문제

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

15761번: Lemonade Line

 

1-1 번역 (GPT 이용)

• 농장에서 뜨거운 여름 날씨다. 농부 존은 N마리의 소들에게 레모네이드를 제공하고 있다! 모든 N마리의 소들(편의상 1...N로 번호 매김)은 레모네이드를 좋아하지만, 그 중 일부는 다른 소들보다 좋아한다. 특히 각 소 i 는 최대 w_i 마리의 소들이 줄을 서 있는 것을 기다릴 수 있다. 현재 모든 N마리의 소들이 들판에 있는 상태이지만, 농부 존이 소 도우미를 불면 소들은 즉시 레모네이드 스탠드로 몰려갈 것이다. 소들은 레모네이드가 서빙되기 전에 모두 도착하지만 두 소가 동시에 도착하지는 않을 것이다. 게다가 소 i 가 도착하면 줄에 가입할 것이며, 이는 오직 이미 줄에 서 있는 소가 최대 w_i 마리일 경우에만 해당된다.
• 농부 존은 미리 어느 정도의 레모네이드를 준비하고 싶지만 낭비하고 싶지 않다. 줄에 가입하는 소의 수는 도착 순서에 따라 달라질 수 있다. 농부 존이 줄에 가입하는 소의 수를 최소화할 수 있는 방법을 찾도록 도와주십시오.
• 힌트 :  이 상황에서는 세 마리의 소만 줄에 서게 될 수 있습니다 (이것이 가장 작은 가능한 수입니다). 먼저 w = 7과 w = 400인 소가 도착하여 줄을 서기로 합니다. 그런 다음 w = 1인 소가 도착하지만, 이미 2마리의 소가 줄에 서 있으므로 가서 물을 받지 않습니다. 그리고 나서 w = 2인 소들이 도착하게 되는데, 한 마리는 줄에 서 있고, 다른 한 마리는 물을 받지 않고 돌아갑니다.

 

2. 풀이

• 문제를 번역해도 이해하기 쉽지 않았다. 저 숫자들을 소들의 인내심으로 생각하니 감을 잡을 수 있었다.
• 예제에서 나온 걸 예로 들자면, 1번째 소는 7만큼 기다릴 수 있고, 2번째 소는 1만큼 기다릴 수 있다는 것으로 해석했다. 그러므로 줄의 길이를 짧게 만들려면 배열을 내림차순으로 정리하고, 인내심을 하나씩 올리면서 진행하는 것으로 했다.
• 반복문의 i 를 인내심 게이지(?) 정도로 보면 될 거 같다.

const [N, ...cows] = require('fs').readFileSync('/dev/stdin').toString().trim().split(/\s/).map(v => +v);
const sortedCows = cows.sort((a,b) => b-a); // 내림차순 정렬
let count = 0; // 줄의 길이를 카운트할 변수.

// 반복문을 돌리면서 i 보다 작다면 count증가!
for(let i = 0; i < sortedCows.length; i++){
  if(i <= sortedCows[i]) count++;
  else break; // i 보다 크게 된다면 카운트할 이유가 없어져서 반복문 종료.
}

console.log(count);