백준 2839번 설탕배달 (JAVA)

문제 : https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

문제설명

 

단순 로직, 메모이제이션, 완전탐색 등 푸는 방법은 여러가지이다.

 

단순 로직은 빠르지만 문제가 달라지면 또 다른 로직을 찾아야한다.

 

완전탐색은 가지치기를 하여도 1초의 제한 시간 내에 풀기 어렵다.

-> 메모이제이션을 이용한다.

 

알고리즘

 

1. 재귀를 통해 memo 배열에 kg의 최적 값을 저장한다.

 

2. memo 배열에 값이 존재할 시 바로 리턴한다.

 

주의사항

 

1. kg이 0 이하가 되면 나누어 떨어지지 않는 것이다.

구현

class Main
{
    static int M;
    static int min;
    static int memo[];
    public static void main(String args[]) throws Exception
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine().trim());
        for (int test_case = 1; test_case <= T; test_case++) 
        {
            M = Integer.parseInt(in.readLine().trim());
            min = Integer.MAX_VALUE; //min이니까 가장 큰값으로 설정
            memo = new int[5001]; //메모이제이션을 위한 변수선언
            int a=0;
            a = solve(0,M); //3의 배수나 5의 배수면 DFS들어간다.
            //삼항연사자 이용해서 출력 min이 아무변화없으면 kg이 0이 안되는 것이고 그것이 아니라면 min 출력
            System.out.println(min == Integer.MAX_VALUE ? -1:min); 
        }
    }

    private static int solve(int cnt, int kg) {
        if(kg < 0)
            return -1; //kg이 0 이하면 의미없음
        if(memo[kg] !=0) //memo[kg]이 0이 아니라면 값이 이미 계산된거
            return memo[kg]; //미리 계산된 값 리턴
        if(kg == 0) //종료조건 kg이 0일때
        {
            if(min > cnt) // 최소 봉지수보다 새로운 봉지가 더 작으면
                min = cnt; //최소 봉지수 갱신
            return cnt; //리턴
        }
        memo[kg] = DFS(cnt+1,kg-5); //최소 봉지를 원하니 큰거부터 재귀
        memo[kg] = DFS(cnt+1,kg-3); //그 다음 작은거
        return 0;
    }

}