[백준 스터디 12주차] 14728번 벼락치기 골드5 - 자바(JAVA)/ Knapsack문제/ 2차원 DP

 

 

 

📑 문제

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

14728번: 벼락치기

문제

ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 같은 힌트를 시험 전에 공지해 주셨다. 내용은 아래와 같다.

1. 여러 단원을 융합한 문제는 출제하지 않는다.
2. 한 단원에 한 문제를 출제한다. 단, 그 단원에 모든 내용을 알고 있어야 풀 수 있는 문제를 낼 것이다.

이런 두가지 힌트와 함께 각 단원 별 배점을 적어 놓으셨다. 어떤 단원의 문제를 맞추기 위해서는 그 단원의 예상 공부 시간만큼, 혹은 그보다 더 많이 공부하면 맞출 수 있다고 가정하자. 이때, ChAOS 회장 일로 인해 힘든 준석이를 위하여 남은 시간 동안 공부해서 얻을 수 있는 최대 점수를 구하는 프로그램을 만들어 주도록 하자.

입력

첫째 줄에는 이번 시험의 단원 개수 N(1 ≤ N ≤ 100)과 시험까지 공부 할 수 있는 총 시간 T(1 ≤ T ≤ 10000)가 공백을 사이에 두고 주어진다.

둘째 줄부터 N 줄에 걸쳐서 각 단원 별 예상 공부 시간 K(1 ≤ K ≤ 1000)와 그 단원 문제의 배점 S(1 ≤ S ≤ 1000)가 공백을 사이에 두고 주어진다.

출력

첫째 줄에 준석이가 얻을 수 있는 최대 점수를 출력한다.

 

 

 

 

 

 

✒️ 풀이

 전형적인 Knapsack(냅색)문제이다.

 사실 난 배낭 문제는 푸는 당시에는 어찌어찌 그렇구나 납득하고 넘어가는데, 머리에 완벽히 녹아들지는 않아서 다시 풀 때가 되면 새로운 유형을 보듯이 낯설다 (ㅎㅎ)

 시뮬레이션 같은건 잘 적응하고 푸는데 이상하게 꼭 못 푸는 문제들이 있다. 80%의 확률로 DP 문제이다.

 

 2차원으로 푸는 이 형식은 템플릿처럼 외워둬서 그대로 적용했고, 문제없이 잘 풀렸다.

 냅색 문제를 풀려면 아래 소스코드 유형은 그대로 외우는 것이 좋다!

 

 

 

 

 

 

 

 

 

💻 소스코드: 자바(Java)

/** knapsack */
public class Main_백준_14728_벼락치기_골드V {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int T = Integer.parseInt(st.nextToken());
		int[][] section = new int[N+1][2];
		
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			int expectTime = Integer.parseInt(st.nextToken());
			int score = Integer.parseInt(st.nextToken());
			section[i][0] = expectTime;
			section[i][1] = score;
		}//input
		
		int[][] dp = new int[N+1][T+1];//1~T까지
		for (int i = 1; i <= N; i++) {//과목별
			int t = section[i][0];
			int score = section[i][1];
			for (int j = 1; j <= T; j++) {
				if(j>=t) {
					dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-t]+score);					
				}else {
					dp[i][j] = dp[i-1][j];
				}
			}
		}
		
		System.out.println(dp[N][T]);
	}//end of main
}//end of class

 

 

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨