백준 2839번 설탕배달-JS

- 처음 시도

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split(' ');
let N = Number(input[0]); //설탕 키로
let count = 0; //상근이가 들고가는 설탕봉지의 수
let remain = 0;
let num = 0;
if(N === 3) {
    count = 1;
} else if(N < 5) {
    count = -1;
} else {
    if((N%5) === 0) {
        count = N/5;
    } else {
        remain = (N%5);
        if((remain%3) === 0) {
            count = Math.floor(N/5) + 1;
        } else if ((remain%3) > 3){
            count = -1;
        } else {
            if((N%3) === 0) {
                count = N/3;
            } else {
                num = N - ((Math.floor(N/5)-1) * 5);
                if(num%3 === 0) {
                    count = Math.floor(N/5)-1 + num/3;
                } else {
                    count = -1;
                }
            }
        }
    }
}

console.log(count);

예외도 없이 아주아주아주 잘 작동했다.(물론 편집기에서만) 왜틀린지 모르겠지만 끊임없는 if문의 향연이여서 이건 아니라고 판단되긴 하다.
문제점: 아 드디어발견. 17같은 경우에서 문제가 발생.
34 + 5인데 내가 짠 코드로 돌려보면 5의 몫이 3보다 작다 -> (5의 몫)-1만큼 N에서 빼고 그 값을 3으로 나눠보자 인데, 5만큼이 아니라 5n(n >= 2)일 경우 제대로 된 값이 나오지 않는다.

- 정답

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split(' ');
const N = Number(input[0]); //설탕 키로
let count = 0;
let sum = N;
while (true) {
    if((sum%5) === 0) {
        count = count + (sum/5);
        console.log('몫:' + sum/5)
        break;
    }  
    sum = sum - 3;
    console.log(sum);
    count++;
    console.log('count: ' + count);
    if(sum < 0) {
        count = -1;
        break;
    }
}

console.log(count);

이것도 사실 살짝 시행착오가 있었다.
이걸 설명하자면
1. 일단 N에서 3을뺀다.
2. 1번의 값이 5의 배수일 경우 count는 이때까지 count + 몫이다.
3. 만약 sum이 0이하가 된다면(5나3으로 떨어지지 않는다면) count = -1

dp풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

let n = Number(input[0]);

const dp = Array(n+1).fill(Infinity);
dp[0] = 0;
dp[3] = 1;
dp[5] = 1;

for(let i=5; i <= n; i++) {
    const three = dp[i-3] === Infinity ? Infinity : dp[i-3];
    const five = dp[i-5] === Infinity ? Infinity : dp[i-5];

    if(three === Infinity && five === Infinity) {
        dp[i] = Infinity;
    } else {
        dp[i] = Math.min(three, five) + 1;
    }
}

console.log(dp[n] === Infinity ? -1 : dp[n]);

제일 작은 것 = 제일 작은 것 + 제일 작은 것 이라 dp배열을 만들고 최소값을 배열의 값으로 줬다.

다른 사람 풀이

• 그리디

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

let n = Number(input[0]);

function solution(n) {
    let answer = 0;

    while (n > 0) {
        console.log('n : ', n, answer);
        if (n % 5 === 0) {
            n -= 5;
        } else {
            n -= 3;
        }
        answer += 1;
    }

    return n === 0 ? answer : -1;
}

console.log(solution(n));

가장 작은 봉지로 배달 해야하므로 최대한 5kg 봉지를 이용해야 하기때문에 5를 먼저 나누는 것

풀이 블로그
설명 참고 블로그