문제
요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.
PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.
•
전설카드
•
레드카드
•
오렌지카드
•
퍼플카드
•
블루카드
•
청록카드
•
그린카드
•
그레이카드
카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.
예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최솟값은 4원이다. 1개 들어있는 카드팩을 4번 사면 된다.
P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 2개 들어있는 카드팩을 2번 사면 4원이고, 이 경우가 민규가 지불해야 하는 금액의 최솟값이다.
카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최솟값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.
입력
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)
둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
출력
첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최솟값을 출력한다.
My solution
예시로 규칙 찾기) N이 4라면?
먼저 1개를 살 때의 최솟값을 위해 비교해야 하는 경우
•
1개를 살 때의 최솟값
•
j : 1 ~ 1/2
따라서 최솟값 배열은 카드팩 배열을 그대로 넣어두면 1번 인덱스를 접근했을 때 그 값이 1개를 살 때의 최솟값이다.
const [N, ...Pack] = i.toString().trim().split(/\s/).map(Number);
const DP = [0, ...Pack];
JavaScript
복사
2개를 살 때의 최솟값을 위해 비교해야 하는 경우
•
2개를 살 때의 최솟값
•
j : 1 ~ 2/2
◦
1개를 살 때의 최솟값 + (2 - 1)개를 살 때의 최솟값
◦
2개를 살 때의 최솟값 + (2 - 2)개를 살 때의 최솟값 // 중복이라 구할 필요 없다.
위의 경우를 비교해서 큰 값을 최솟값 배열의 2번 인덱스에 업데이트한다.
3개를 살 때의 최솟값을 위해 비교해야 하는 경우
•
3개를 살 때의 최솟값
•
j : 1 ~ 3/2
◦
1개를 살 때의 최솟값 + (3 - 1)개를 살 때의 최솟값
◦
2개를 살 때의 최솟값 + (3 - 2)개를 살 때의 최솟값 // 중복이라 구할 필요 없다.
◦
3개를 살 때의 최솟값 + (3 - 3)개를 살 때의 최솟값 // 중복이라 구할 필요 없다.
위의 경우를 비교해서 큰 값을 최솟값 배열의 3번 인덱스에 업데이트한다.
4개를 살 때의 최솟값을 위해 비교해야 하는 경우
•
4개를 살 때의 최솟값
•
j : 1 ~ 4/2
◦
1개를 살 때의 최솟값 + (4 - 1)개를 살 때의 최솟값
◦
2개를 살 때의 최솟값 + (4 - 2)개를 살 때의 최솟값
◦
3개를 살 때의 최솟값 + (4 - 3)개를 살 때의 최솟값 // 중복이라 구할 필요 없다.
◦
4개를 살 때의 최솟값 + (4 - 4)개를 살 때의 최솟값 // 중복이라 구할 필요 없다. 범위의 절반만 반복
위의 경우를 비교해서 큰 값을 최솟값 배열의 4번 인덱스에 업데이트한다.
Code
const solution = function (i) {
const [N, ...Pack] = i.toString().trim().split(/\s/).map(Number);
const DP = [0, ...Pack];
for (let i = 2; i <= N; i++) {
// 범위 제한으로 중복 연산 제거
for (let j = 1; j <= i / 2; j++) {
DP[i] = Math.min(DP[i], DP[j] + DP[i - j]);
}
}
console.log(DP[N]);
return DP[N];
};
describe('카드 구매하기 2', () => {
it('TC1', () => {
expect(
solution(`4
1 5 6 7`)
).toStrictEqual(4);
});
it('TC2', () => {
expect(
solution(`5
10 9 8 7 6`)
).toStrictEqual(6);
});
it('TC3', () => {
expect(
solution(`10
1 1 2 3 5 8 13 21 34 55`)
).toStrictEqual(5);
});
it('TC4', () => {
expect(
solution(`10
5 10 11 12 13 30 35 40 45 47`)
).toStrictEqual(26);
});
it('TC5', () => {
expect(
solution(`4
5 2 8 10`)
).toStrictEqual(4);
});
it('TC6', () => {
expect(
solution(`4
3 5 15 16`)
).toStrictEqual(10);
});
});
JavaScript
복사
