문제
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.
첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)
어떻게 풀었나
가장 적은 수의 설탕 포대를 옮기고 싶다면 5키로그램짜리를 최대한 넣어주면 된다.
input으로 받는 그람수와 딱 떨어져야하니 5키로그램짜리를 최대 개수에서 3으로 나누어 떨어지는 구간까지 감소시켜가며 찾는다.
5키로 개수가 확정되면 계산식으로 3키로의 개수를 구한 후 3으로도 나누어 떨어지지 않으면 -1을 출력하고 아니면 총 개수를 출력한다.
var sugar_kgram = 11; // parseInt(input) ;
var five_max = Math.trunc(sugar_kgram / 5);
var five_kgram_cnt = 0;
var i=0;
for (i = five_max; i >= 0; i--){
if ((sugar_kgram - (i * 5)) % 3 == 0) {
five_kgram_cnt = i;
break;
}
}
three_kgram_cnt = (sugar_kgram - (five_kgram_cnt * 5)) / 3;
console.log(
Number.isInteger(three_kgram_cnt) == false ? -1 : five_kgram_cnt + three_kgram_cnt);다른 사람과 비교
다른 분이 정리해 둔 것을 봤는데 해결 법에는 그리디한 방식과 dp방식이 있다고 한다.
나는 짧은 시간 안에 풀어야 하는 경우 바로바로 최적의 방법을 선택하려고 하는 경향이 커서 그리디하게 한 것 같다.
또한 그리디 방식도 나는 cnt변수들로 계산하는 식으로 처리했는데 전체 수에서 빼가면서 구하기도 했다. 이게 더 직관적으로 보여서 한 번 다시 구현해보기로 했다. (지금보니까 왜이리 복잡하게 푼거지;;)
dp방식은 아직 잘 모르기도 하고. 나중에 해당 파트 풀 기간에 하려고 했지만 오늘 간단하게 한 번 훑기로 했다.
더 직관적으로 수정해보자
3을 빼다가 5의 배수가 되면 그 개수만큼 더하고 끝나는 아주 직관적이고 깔끔한 알고리즘이 완성됐다. 이걸 보고나서 내가 푼 걸 보니까 너무 지저분해보인다...ㅠ
속도는 미세하게 위에 푼게 빠르긴 한데 아마 5키로를 먼저 구하기 때문에 반복문을 조~금 덜 돌기 때문인 것 같다.
var sugar_kgram = 11;
var cnt = 0;
while (sugar_kgram > 0) {
if (sugar_kgram % 5 == 0) {
var five_kgram = sugar_kgram / 5;
cnt += five_kgram;
sugar_kgram = 0;
}
else {
sugar_kgram -= 3;
cnt++;
}
}
console.log(sugar_kgram< 0? -1 : cnt);dynamic programming
큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다.
분할정복(divide and conquer)도 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이지만 다이나믹 프로그래밍은 작은 문제의 중복이 안되고, 분할정복은 중복이 가능하다.
dp로 풀 수 있는 문제의 속성
겹치는 부분 문제가 있는 경우
큰 문제를 작은 문제로 쪼갤 수 있다. 대표적으로 피보나치 수열이 있다.
피보나치 수열의 큰 문제를 작은 문제로 나누기
큰 문제 : n번째 피보나치 수를 구하는 문제 작은 문제 : n-1번째 피보나치 수를 구하는 문제 ...
최적화 부분 구조
작은 문제 해결로 큰 문제 정답을 구할 수 있다.
푸는 방식
작은 문제는 한 번만 풀기 위해 배열을 통해 메모(Memozation)을 사용한다.
dp방식은 한 번 훑는 정도로 바로 응용하기는 힘든 것 같다. 후에 dp파트 기간에 공부해서 다시 풀어보겠다!
당분간 수학 카테고리 문제를 쉽든 어렵든 빨리 푸는 연습을 해야겠다.
