.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
DP, greedy 211026
문제
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)
출력
상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.
예제 입력 1
18
Plain Text
복사
예제 출력 1
4
Plain Text
복사
예제 입력 2
4
Plain Text
복사
예제 출력 2
-1
Plain Text
복사
예제 입력 3
6
Plain Text
복사
예제 출력 3
2
Plain Text
복사
예제 입력 4
9
Plain Text
복사
예제 출력 4
3
Plain Text
복사
예제 입력 5
11
Plain Text
복사
예제 출력 5
3
Plain Text
복사
my solution
이와 비슷한 다이나믹 프로그래밍 문제는 동전교환(냅색 알고리즘)이 대표적이다.
여러 단위의 동전이 주어졌을 떄, 거스름돈을 가장 적은 수의 동전으로 교환해주는 방법을 찾는 것이다. 각 동전은 무한정 사용할 수 있다.
여기서는 단위까지도 입력으로 보내준다. 그래서 for문으로 값을 하나씩 내려줘야해서 시간복잡도가 O(n^2)이 된다.
마찬가지로 이 문제에서는 3킬로그램과 5킬로그램 단위의 봉지가 주어진다. 최소 개수로 사용해서 배달해야 한다.
미리 전달하고 싶은 N킬로그램 + 1 만큼의 길이로 배열을 만든다.
이 배열의 초기값을 알고 있는 값으로 넣어준다. 이 값이 반복적으로 사용되면서 앞에서부터 값을 채워나간다.
배열의 각 인덱스가 숫자를 뜻하기 때문에 인덱스별로 봉지가 더 적게 사용됐다면 그것으로 값을 변경시킨다.
let answer = "-1";
let dy = [...Array(parseInt(N) + 1)].fill(1000);
dy[0] = 0;
for (let j = 3; j <= N; j++) {
dy[j] = Math.min(dy[j], dy[j - 3] + 1);
}
for (let j = 5; j <= N; j++) {
dy[j] = Math.min(dy[j], dy[j - 5] + 1);
}
dy = dy.map((v) => (v === 1000 ? -1 : v));
console.log(dy[N]);
return dy[N].toString(); // 테스트용
JavaScript
복사
이렇게 해서 테스트 코드를 돌려보면 전부 패스가 된다.
하지만 제출하면 틀렸다고 나온다. 백준은 콘솔을 안 찍어주기 때문에 혼자 유추해야 한다.
어떤 방법으로 해야 하는지 이전에 배웠던 DP 풀이법대로 풀리지 않아서 계속 같은 구조에서 갇혀있었는데 다른 사람의 풀이를 보고 방식을 바꾸었다.
각 단위를 알고 있는 상태에서 while문으로 조건에 도착할 때까지 반복한다.
N을 3으로 계속 빼줘서 5킬로그램을 사용할 수 없는 숫자에서 벗어난 다음(5로 나눠지는 값을 찾았을 때 더이상 3킬로 봉지를 쓸 필요가 없다.) N이 5로 나눠지면 5킬로그램인 봉지로 담는 게 무조건 이득이다. 이렇게 3으로 뺀 횟수와 마지막에 5로 나눠진 몫으로 최소 개수가 계산된다.
while (1) {
if (N % 5 === 0) {
unit5 = N / 5;
console.log(unit5 + unit3);
break;
// return unit5+unit3;
}
(...)
N -= 3;
unit3++;
}
JavaScript
복사
3으로 뺄(나눌) 수가 없고(3으로 나눠지지 않는 N이면 뺐을 때 음수가 되버린다. 아래의 조건문이 이 N을 처리해준다.), 5로 나눠지지 않는 값을 잡기 위해 while문 안에 아래의 조건을 추가한다.
if (N < 0) {
console.log(-1);
break;
}
JavaScript
복사
다이나믹 프로그래밍 문제인 동전 교환과 너무 유사한 문제라 비슷하게 풀어보려고 했는데 DP답게 메모이제이션을 사용하기 위해서 기존의 값을 배열에 저장했다가 다시 쓰는 식으로 풀었던 것이 너무 불필요한 과정이었던 것 같다.
수학적으로 좀더 고민해서 더 쉬운 방식이 있다면 그 방식을 먼저 적용해봐야겠다.
소스코드
function solution(N) {
let unit3 = 0;
let unit5 = 0;
while (1) {
if (N % 5 === 0) {
unit5 = N / 5;
console.log(unit5 + unit3);
break;
// return unit5+unit3;
}
if (N < 0) {
console.log(-1);
break;
// return -1;
}
N -= 3;
unit3++;
}
}
test("solution", () => {
expect(solution("18")).toStrictEqual("4");
expect(solution("4")).toStrictEqual("-1");
expect(solution("6")).toStrictEqual("2");
expect(solution("9")).toStrictEqual("3");
expect(solution("11")).toStrictEqual("3");
});
JavaScript
복사
