14728번: 벼락치기 - DP 냅색(배낭) 알고리즘 C++

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

14728번: 벼락치기

 

1. 문제설명

첫째 줄에는 이번 시험의 단원 개수 N(1 ≤ N ≤ 100)과

시험까지 공부 할 수 있는 총 시간 T(1 ≤ T ≤ 10000)가 공백을 사이에 두고 주어진다.

둘째 줄부터 N 줄에 걸쳐서 각 단원 별 예상 공부 시간 K(1 ≤ K ≤ 1000)와

그 단원 문제의 배점 S(1 ≤ S ≤ 1000)가 공백을 사이에 두고 주어진다.

 

각 문제는 한번 씩만 풀 수 있고 최대 점수를 구해야 한다.

 

 

2. 접근 방법[알고리즘]

각 문제는 한 번만 풀 수 있으므로

다이나믹 테이블 dy에 for문을 뒤부터 돌면서

최댓값을 누적해주면 된다.

 

for문을 뒤부터 도는 이유는

이 문제는 각 단원 문제를 단 한 번씩 풀 수 있는데

앞에서부터 돌면 계속해서 중복된 값을 더해서 누적하기 때문이다.

중복된 값을 누적하는 걸 피하기 위해 뒤부터 돈다.

 

만약 각 단원 문제를 여러번 풀 수 있다면

for문을 앞에서 부터 돌아 계속 중복해서 누적해주면 된다.

 

 

3. 문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, t, dy[10001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> t;
	for (int i = 0; i < n; i++) {
		int k, s;
		cin >> k >> s;
		for (int j = t; j >= k; j--) {
			dy[j] = max(dy[j], dy[j - k] + s);
		}
	}
	cout << dy[t];

}

백준 14728 풀이