BOJ - 2839 설탕 배달

문제 링크 : https://www.acmicpc.net/problem/2839

문제 유형 : 그리디 알고리즘

문제 티어 : 실버4

문제 풀이 : 5키로랑 3키로짜리 봉지가 있고 이 두 개를 통해 최대한 적은 갯수의 봉지를 가져가야 한다. 

 => 5키로로 담을 수 있는 만큼 담고 그 다음 3키로로 채우면 될 것 같은 문제다. 

시간 복잡도 : O(N)

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let n = Number(input[0]);
let count = 0;
while(true) { 
   if(n%5===0){
        count -= n/5;
        break;
    }
    n-=3;
    count++;
    if(n<0){
        count=-1;
     }
}
console.log(count);

 

 

2) GPT 해설 (GPTs 링크 : https://chatgpt.com/g/g-uWf5rBEwE-baegjun-algorijeum-bbusyeobbusyeo

ChatGPT - 백준 알고리즘 뿌셔뿌셔

 

 

문제 설명

설탕 N kg을 배달해야 합니다. 이때, 3kg 봉지와 5kg 봉지를 최소한으로 사용하여 정확히 N kg을 만들 수 있는 봉지의 수를 구하는 문제입니다. 만약 정확히 N kg을 만들 수 없다면 -1을 출력해야 합니다.

문제 접근 방법

1. 그리디 알고리즘:
   • 5kg 봉지를 최대한 많이 사용하고, 남은 설탕을 3kg 봉지로 채워 나갑니다.
   • 먼저 5kg 봉지로 최대한 나눠 보고, 나머지 설탕을 3kg 봉지로 나눠지게 할 수 있는지 확인합니다.
   • 5kg 봉지를 하나씩 줄여가며 남은 설탕을 3kg 봉지로 채울 수 있는지 반복적으로 확인합니다.

단계별 문제 풀이

1. 5kg 봉지로 최대한 나누기:
   • 주어진 설탕의 무게 N을 5kg으로 나누어 사용 가능한 5kg 봉지의 최대 개수를 구합니다.
2. 3kg 봉지로 나머지 채우기:
   • 5kg 봉지로 나눈 나머지 설탕을 3kg 봉지로 나눌 수 있는지 확인합니다.
   • 만약 나눌 수 있다면, 그때의 5kg 봉지 개수와 3kg 봉지 개수의 합이 답이 됩니다.
   • 나눌 수 없다면 5kg 봉지의 개수를 하나 줄이고 다시 3kg 봉지로 나누는 과정을 반복합니다.
3. 불가능한 경우 확인:
   • 위 과정을 통해도 정확히 N kg을 만들 수 없다면 -1을 출력합니다.

예제 입력 및 설명

예를 들어, N = 18인 경우:

• 5kg 봉지 3개와 3kg 봉지 1개로 18kg을 만들 수 있습니다. 답은 4개입니다.

단계별 풀이 과정

1. 초기 변수 설정:
   • N을 입력받습니다.
   • 5kg 봉지의 최대 개수를 계산합니다.
2. 반복문을 통해 봉지 개수 계산:
   • 5kg 봉지의 개수를 최대한 사용하면서 남은 설탕을 3kg 봉지로 나눌 수 있는지 확인합니다.
   • 만약 남은 설탕이 3kg으로 나눠진다면, 총 봉지 개수를 계산하여 출력합니다.
   • 그렇지 않으면, 5kg 봉지의 개수를 하나 줄이고 다시 시도합니다.
   • 반복문이 종료될 때까지 나누어지지 않으면 -1을 출력합니다.

예제 코드 (JavaScript)

let count = 0;

while (N >= 0) {
    if (N % 5 === 0) {
        count += Math.floor(N / 5);
        return count;
    }
    N -= 3;
    count++;
}

return -1;

코드 설명

1. findMinBags 함수는 설탕의 무게 N을 받아서 최소 봉지 수를 반환합니다.
2. while 문을 사용하여 남은 설탕이 0 이상일 때까지 반복합니다.
3. if 문을 사용하여 남은 설탕이 5로 나누어떨어지면, 현재까지의 봉지 수에 5kg 봉지의 개수를 더하여 반환합니다.
4. 그렇지 않으면, 3kg 봉지를 하나 사용하고 카운트를 증가시킵니다.
5. 반복문이 종료되면 정확히 N kg을 만들 수 없으므로 -1을 반환합니다.