DP 제일 위에 있는 문제를 풀어보았다.
3kg과 5kg의 설탕으로 목표 무게를 만드는 것이다. 만들지 못하면 -1을 만들 수 있으면, 최소한의 수의 설탕으로
목표 무게를 만드는 것이다.
메모제이션을 이용하여 0부터 목표 무게까지 최소한의 수를 쌓아가면 된다.
0 = -1
1 = -1
2 = -1
3 = 1
4 = -1
5 = 1
은 기저 조건으로 설정한다. 만약 기저 조건보다 낮은 목표 무게가 있다면 예외 처리를 한다.
그리고, 이제 무게를 6부터 쌓아갈 때 3을 뺀 수와 5를 뺀 무게 중,
적은 수의 설탕 봉지를 쓴 경우를 택해 1을 더하면 된다.
또한, 15같은 무게는 3kg으로도 5kg으로도 만들 수 있다.
이런 경우를 생각해 3kg을 쓴 경우와 5kg을 쓴 경우 모두를 생각해 비교해야 한다.
다음은 Java로 작성한 코드이다.
import java.util.Scanner;
public class Sugar {
final static int SMALL_SUGAR = 3;
final static int LARGE_SUGAR = 5;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
//정답 저장 배열
int[] solution = new int[n+1];
//기저 조건 예외 처리
if(n > 5) {
//기저 조건 설정
solution[0] = -1;
solution[1] = -1;
solution[2] = -1;
solution[3] = 1;
solution[4] = -1;
solution[5] = 1;
//DP
for (int i = 6; i <= n; i++) {
//3을 사용한 경우
if(solution[i-SMALL_SUGAR] != -1) {
if(solution[i-LARGE_SUGAR] != -1) {
solution[i] = Math.min(solution[i-SMALL_SUGAR], solution[i-LARGE_SUGAR]) + 1;
}else {
solution[i] = solution[i-SMALL_SUGAR] + 1;
}
//5를 사용한 경우
}else if(solution[i-LARGE_SUGAR] != -1) {
if(solution[i-SMALL_SUGAR] != -1) {
solution[i] = Math.min(solution[i-SMALL_SUGAR], solution[i-LARGE_SUGAR]) + 1;
}else {
solution[i] = solution[i-LARGE_SUGAR] + 1;
}
//둘 다 해당되지 않는 경우
}else {
solution[i] = -1;
}
}
System.out.println(solution[n]);
}else if(n == 3 || n == 5){
System.out.println(1);
}else {
System.out.println(-1);
}
}
}
