[ 백준_11256 ] 사탕 ( 그리디 - 자바스크립트 )

문제

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

11256번: 사탕

 

문제를 이해했는지?

 

각 상자의 넓이와 높이, 그리고 보내고자 하는 사탕의 개수가 주어 졌을 때 포장 가능한 최소한의 박스 수를 출력하시오.

 

풀이방법 - 그리디

function solution() {
  let count = 0;
  let sum_weight = 0;
  const new_box = [];
	
  // 가로 * 세로로 박스가 담을 수 있는 사탕의 수를 계산
  box_sizes.forEach((each) => {
    new_box.push(each[0] * each[1]);
  });
	
  // 내림차순으로 정렬
  new_box.sort((a, b) => b - a);

  for (let i = 0; i < new_box.length; i++) {
    sum_weight += new_box[i];
    count += 1;
	// 박스의 크기로 j보다 많이 담을 수 있으면 개수를 출력
    if (sum_weight >= candies) {
      return console.log(count);
    }
  }
}

const [candies, box_count] = [20, 5];

const box_sizes = [
  [3, 4],
  [2, 5],
  [1, 8],
  [3, 3],
  [2, 5],
];

solution();

 

 

아래 코드는, 주어진 개수와 정확히 맞추도록 설계한 알고리즘이다. 궁금해서 더 짜본게 아니라 문제 이해를 ㅎㅎ..

function solution() {
  let count = 0;
  let sum_weight = 0;
  const new_box = [];

  box_sizes.forEach((each) => {
    new_box.push(each[0] * each[1]);
  });

  new_box.sort((a, b) => b - a);

  for (let i = 0; i < new_box.length; i++) {
    sum_weight += new_box[i];
    count += 1;

    if (sum_weight > candies) {
      sum_weight -= new_box[i - 1];
      count -= 1;
      continue;
    }

    if (sum_weight === candies) {
      return console.log(count);
    }
  }
}

const [candies, box_count] = [20, 5];

const box_sizes = [
  [3, 4],
  [2, 5],
  [1, 8],
  [3, 3],
  [2, 5],
];

solution();