[백준] 12018 Yonsei TOTO - 완전탐색(BruteForce) + 그리디(greedy, 탐욕법) + 정렬(Sort) 동적계획법(Dynamic Programming, DP) JAVA

https://www.acmicpc.net/problem/12018

코드설명

완전탐색(BruteForce) + DFS(깊이우선탐색) + 동적계획법(Dynamic Programming, DP) 를 활용합니다.

 

문제를 완전탐색으로 접근했습니다. 다른 방법은 생각나지 않았습니다.

문제에서 N은 100이므로, 2^100 개의 탐색결과가 나와 시간초과가 발생할 수 있지만, 메모이제이션(Cache)를 적용하여 개선할 수 있습니다.

 

문제에서 4%에서 계속 틀렸었는데, 문제를 잘못읽었습니다.

처음에 만약 수강신청한 인원보다 과목 수강인원이 많다면, 마일리지를 0 원쓰고 들을 수 있다고 생각했습니다.

하지만, 문제에서 마일리지는 반드시 1~36 까지의 마일리지를 사용해야한다고 나옵니다.

//만약 선택한사람이 더 적다면,(수강인원이 더 많다면, 마일리지를 하나도 안쓰고 참여가능)
if(L[level] > arr[level].length) return selectCache[level] = 1;

 

코드

정답코드입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    private static int N, T, K, M;
    private static int[][] arr;
    private static int[] L;
    private static int[][] cache;
    private static int[] selectCache;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		cache = new int[N+1][M+1];
		selectCache = new int[N+1];
		Arrays.fill(selectCache, -1);
		for(int i=0;i<=N;i++) {
			Arrays.fill(cache[i], -1);
		}
		arr = new int[N][];
		L = new int[N];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			int P = Integer.parseInt(st.nextToken());
			L[i] = Integer.parseInt(st.nextToken());
			arr[i] = new int[P];

			st = new StringTokenizer(br.readLine());
			for(int j=0;j<P;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
			Arrays.sort(arr[i]);
		}
		
		System.out.println(func(0, M));
		
    }
    
    private static int func(int level, int mile) {
    	if(level == N) {
    		return 0;
    	}

    	if(cache[level][mile] != -1) return cache[level][mile];
    	
    	int ret = 0;
    	//선택안할경우
    	ret = Math.max(ret, func(level + 1, mile) + 0);
    	
    	//선택할경우
    	int cost = calculateCost(level);
    	if(mile - cost >= 0) {
//    		System.out.println("level:"+level+"cost:"+cost);
    		ret = Math.max(ret, func(level + 1, mile-cost) + 1);
    	}
    	
    	return cache[level][mile] = ret;
    }
    
    private static int calculateCost(int level) {
    	if(selectCache[level] != -1) return selectCache[level];
    	//만약 선택한사람이 더 적다면,(수강인원이 더 많다면, 마일리지를 하나도 안쓰고 참여가능)
    	if(L[level] > arr[level].length) return selectCache[level] = 1;
    	
    	int cnt = 0;
    	int cost = 0;
    	for(int i=arr[level].length - 1;i>=0;i--) {
    		cnt += 1;
    		if(L[level] == cnt) {
    			cost = arr[level][i];
    			break;
    		}
    	}
    	return selectCache[level] = cost;
    }
    
    
}

처음에 시간초과 난 코드였다가 DP를 적용해서 시간초과를 해결했으나 4%에서 틀립니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    private static int N, T, K, M;
    private static int[][] arr;
    private static int[] L;
    private static int[][] cache;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		cache = new int[N+1][M+1];
		for(int i=0;i<=N;i++) {
			Arrays.fill(cache[i], -1);
		}
		arr = new int[N][];
		L = new int[N];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			int P = Integer.parseInt(st.nextToken());
			L[i] = Integer.parseInt(st.nextToken());
			arr[i] = new int[P];

			st = new StringTokenizer(br.readLine());
			for(int j=0;j<P;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
			Arrays.sort(arr[i]);
		}
		
		System.out.println(func(0, M));
		
    }
    
    private static int func(int level, int mile) {
    	if(level == N) {
    		return 0;
    	}

    	if(cache[level][mile] != -1) return cache[level][mile];
    	
    	int ret = 0;
    	//선택안할경우
    	ret = Math.max(ret, func(level + 1, mile) + 0);
    	
    	//선택할경우
    	int cost = greedySelect(level);
    	if(mile - cost >= 0) {
    		ret = Math.max(ret, func(level + 1, mile-cost) + 1);
    	}
    	
    	return cache[level][mile] = ret;
    }
    
    private static int greedySelect(int level) {
    	//만약 선택한사람이 더 적다면,
    	if(L[level] > arr[level].length) return 0;
    	
    	int cnt = 0;
    	int cost = 0;
    	for(int i=arr[level].length - 1;i>=0;i--) {
    		cnt += 1;
    		if(L[level] == cnt) {
    			cost = arr[level][i];
    			break;
    		}
    	}
    	return cost;
    }
    
    
}