[백준] 2839번 설탕 배달 (java)

www.acmicpc.net/problem/2839

2839번: 설탕 배달

완전탐색 + 메모이제이션 기법을 사용 

만약 같은 무게를 다시 재귀로 들어올 경우 기존보다 사용한 봉지의 수가 더 작을 경우만 vis[해당무게]를 업데이트하고 완전 탐색을 돌려준다. 만약 같은 무게인데 사용한 봉지의 수가 더 많은 경우는 더이상 검사할 필요가 없다.

 

import java.util.Scanner;

public class Main {
	static int n;
	static int ans=Integer.MAX_VALUE;
	static int[] vis=new int[5001];
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		subset(0,n);
		System.out.println(ans==Integer.MAX_VALUE?-1:ans);
	}
	private static void subset(int cnt, int weight) {
		if(weight==0) {
			ans=Math.min(ans, cnt);
			return;
		}
		if(weight-3>=0) {
			if(vis[weight-3]==0 || vis[weight-3]>cnt+1) {
				vis[weight-3]=cnt+1;
				subset(cnt+1,weight-3);
			}
			
		}
		if(weight-5>=0) {
			if(vis[weight-5]==0 || vis[weight-5]>cnt+1) {
				vis[weight-5]=cnt+1;
				subset(cnt+1,weight-5);
			}
			
		}

	}
}