[Softeer] 택배 마스터 광우 JS

https://softeer.ai/practice/6273 

 

여름 휴가를 떠나기 위해 용돈이 필요했던 광우는 H택배 상하차 아르바이트를 지원 했다. 광우는 평소에 운동을 하지않아 힘쓰는 데에 자신이 없었지만, 머리 하나 만큼은 비상해 택배가 내려오는 레일의 순서를 조작해서 최소한의 무게만 들 수 있게 일을 하려고 한다.

레일은 N개이며, 각각의 레일은 Ni 무게 전용 레일로 주어진다. (같은 무게의 레일은 주어지지 않는다.) 레일의 순서가 정해지면 택배 바구니 무게(M)를 넘어가기 전까지 택배 바구니에 택배를 담아 들고 옮겨야 한다. 레일 순서대로 택배를 담되, 바구니 무게를 초과하지 않은 만큼 담아서 이동하게 되면 1번 일한 것으로 쳐준다. (단, 택배는 순서대로 담아야 하므로 레일의 순서를 건너 뛰어 담을 수는 없다)

총 K번 일을 하는데 최소한의 무게로 일을 할 수 있게 광우를 도와주는 프로그램을 만들어 보자.

제약조건

3 ≤ N ≤ 10

max(Ni) < M ≤ 50

1 ≤ K ≤ 50

1 ≤ Ni ≤ 50

입력형식

첫째 줄에는 레일의 개수 N, 택배 바구니의 무게 M, 일의 시행 횟수 K가 주어진다. 그 다음 줄에는 Ni개의 택배 레일의 전용 무게가 주어진다. (택배 바구니는 무조건 택배보다 작은 경우는 없다.)

출력형식

출력으로는 광우가 일 해야하는 최소한의 택배 무게를 출력한다.

입력예제1

5 20 4 5 8 10 19 7

출력예제1

54

 

 

레일의 개수가 5개이고 택배 바구니의 무게를 20, 일을 시행해야 하는 횟수를 4번 이라고 했을 때, 레일의 순서가 | 5 | 8 | 10 | 19 | 7 | 이 된다면 총 4번 수행 했을 때 답은 62가 된다.

 

1번 (5+8)

2번 (5+8) + (10)

3번 (5+8) + (10) + (19)

4번 (5+8) + (10) + (19) + (7+5+8) = 62

 

하지만 최적의 순서는 | 5 | 10 | 8 | 19 | 7 | 이 된다.

 

1번 (5+10)

2번 (5+10) + (8)

3번 (5+10) + (8) + (19)

4번 (5+10) + (8) + (19) + (7+5) = 54

입력예제2

9 25 50 1 21 2 22 3 23 4 24 10

출력예제2

772

 

---

 

문제요점

N개 레일, K번 일함, 한 바구니에 최대 M만큼 담을수 있다 
N개의 레일의 순서에 따라 총 옮기는 택배무게가 다른데, 
최소한으로 택배 무게를 옮길때의 택배무게를 출력해라

 

JS풀이

• 레일이 10개 이하이므로 모든 레일의 조합을 구한다
• 매 조합마다 K번 일할 때 옮기는 무게를 구하고 최소무게를 갱신한다.
  • 현재상자를 바구니에 담을 수 있으면
    • 바구니 무게 += 상자무게 를 추가하고
    • 현재 조합배열 뒤에 다시 이 상자무게를 추가한다 (K번 바구니를 채울떄까지 순열은 중복해야하기 떄문이다)
    • i++하여 다음 상자를 가리킨다
  • 현재상자를 넣을시 바구니의 최대무게를 초과하면
    • 이제까지 옮긴무게 += 현재 바구니 안의 무게 를 추가하고
    • 현재 바구니를 비운다
    • K-- 남은 일할 횟수를 줄인다

 

const readline = require('readline');
const rl = readline.createInterface({
    input : process.stdin,
    output : process.stdout
});

const lines = [];

// input
rl.on('line', input => {
	// 여기에서 input은 문제에 제시된 입력예시가 string형태로 한 줄씩이다
    lines.push(input.split(' ').map(e => parseInt(e)))
})

// output
rl.on('close', () => {
    let answer = Infinity;
    const [railCount, maxWeight, tryCount] = lines[0];
    const weights = lines[1];
    const permutations = getPermutation(weights, railCount);

    for (const permutation of permutations) {
        let workCount = tryCount;
        let currBuketW = 0;
        let sum = 0;
        let i = 0;
        while(workCount > 0) {
            const currW = permutation[i];
            // 최대무게를 초과하지 않은 경우
            if (currBuketW + currW <= maxWeight) {
                currBuketW += currW;
                permutation.push(currW);
                i++;
            } 
            // 최대 무게를 초과한 경우
            else {
                workCount--;
                sum += currBuketW;
                currBuketW = 0; // 바구니를 비운다
            }
        }
        answer = Math.min(answer, sum);
    }
    console.log(answer);
    process.exit();
})


function getPermutation(arr, count) {
    const result = [];
    if (count === 1) {
        return arr.map(e => [e]);
    }
    arr.forEach((e, i) => {
        const selected = e;
        const newArr = arr.filter(e => e !== selected);
        // 선택된 걸 제외한 남은 것들로 만든 순열을 구한다
        const remainedPermutation = getPermutation(newArr, count-1);
        // 선택된것과 남은 것으로 만들어진 순열을 합친다
        remainedPermutation.forEach(e => {
            result.push([selected, ...e]);
        })
    })
    return result;
}

 

 

VS code에서는 주어진 테스트 케이스를 통과했는데, 소프티어에서는 시간초과가 났다. 

 

 

 

 

 

파이썬 코드 참고

https://jie0025.tistory.com/454