[BOJ-Silver2] 16493번 최대 페이지 수

💡 첫번째 풀이

✔️ 완전탐색 + 백트래킹

• 조합 알고리즘 사용
• 챕터를 조합으로 하나씩 선택 후 읽는 데 소요되는 시간 계산
• 그 시간이 n보다 작거나 같을 경우 현재 result랑 비교해서 최대값 갱신
• n, m이 작아서 가능한 풀이

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

public class Main {
	static int n, m;
	static int[] days;
	static int[] pages;
	static int result = 0;

	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()); // 챕터 수

		days = new int[m];
		pages = new int[m];
		for(int i = 0; i<m; i++){
			st = new StringTokenizer(br.readLine());
			days[i] = Integer.parseInt(st.nextToken());
			pages[i] = Integer.parseInt(st.nextToken());
		}

		boolean[] visited = new boolean[m];
		combination(visited, 0, 0);
		System.out.println(result);

	}

	public static void combination(boolean[] visited, int start, int daySum){
   		// 현재까지 걸린 일 수(daySum)이 n 이하일 때 페이지 계산
		if (daySum <= n){
			int page = 0;
			for(int i = 0; i<m; i++){
				if (visited[i]){
					page += pages[i];
				}
			}
			result = Math.max(result, page);
		} else {
			return;
		}

		for(int i = start; i<m; i++){
			if (!visited[i]){
				visited[i] = true;
				combination(visited, i+1, daySum+days[i]);
				visited[i] = false;
			}
		}
	}
}

💡 두번째 풀이

✔️ DP

• 배낭 알고리즘 사용
• dp[i][j] = i번째 챕터까지 고려했을 때, j일 안에 읽을 수 있는 최대 페이지 수
• dp[i][j] = Math.max(dp[i-1][j], dp[i-1]j - days[i]] + pages[i])

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

public class Main {
	static int n, m;
	static int[] days;
	static int[] pages;

	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()); // 챕터 수

		days = new int[m+1];
		pages = new int[m+1];
		for(int i = 1; i<=m; i++){
			st = new StringTokenizer(br.readLine());
			days[i] = Integer.parseInt(st.nextToken());
			pages[i] = Integer.parseInt(st.nextToken());
		}

		// dp[i][j] = i번째 챕터까지 고려했을 때, j일 안에 읽을 수 있는 최대 페이지 수
		int[][] dp = new int[m+1][n+1];
		for(int i = 1; i<=m; i++){
			for(int j = 0; j<=n; j++){
				if (days[i] <= j){
					dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-days[i]] + pages[i]);
				} else {
					dp[i][j] = dp[i-1][j];
				}
			}
		}
		System.out.println(dp[m][n]);

	}
}