[백준/C++] 벼락치기 (No. 14728)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 기준만 잘 잡으면 풀 수 있다.

 

공부할 수 있는 최대 시간이 10000이므로 아래와 같은 배열을 하나 만든다.

fig

 

 

이 배열은 T시간동안 공부했을 경우 얻을 수 있는 점수의 최대값을 저장하는 배열이다.

그리고 전부 -1로 초기화를 한 다음 시간이 0 인 경우만 0으로 초기화한다.

여기서 DP[T] = -1일 경우는 현재  T시간을 공부하는 방법이 없다는 뜻이다.

 

 

그 후 입력을 받아 n개의 공부의 값을 이용해 위 배열을 채워나가면 된다.

(이때, 과목에 대한 시간 = E, 성과 = V라고 하자)

 

10,000 부터 0 까지 for문을 돌리면서 만약 저장된 값이 -1이 아니라면, 방문할 수 있으므로

DP[T+E] = max(DP[T+E], DP[T] +V) 를 계산해나가면 된다.

 

거꾸로 탐색하는 이유는 1차원 배열만 이용하기 때문이다.

 

앞에서부터 탐색할 경우 DP[T+E]를 계산한 다음 DP[T+E+E] 를 계산하게 되면 한 과목을 두번 공부한 결과가 저장되는 경우가 생길 수 있기 때문이다.

 

이를 방지하기 위해서는 배열을 더 사용해야 하는데, 나는 1차원 크기의 배열 하나로 문제를 풀기 위해 거꾸로 탐색을 했다.

 

 

+ 실제로는 10,000의 크기가 아닌 T+1크기의 배열을 만들면 된다.

어차피 T시간 이상 공부할 수 없기 때문이다. 

 

 

 

[아이디어 정리]

1. 공부시간의 크기를 가진 배열을 하나 만든다.
2. 거꾸로 탐색을 하면서 공부시간에 따라 얻을 수 있는 점수의 최댓값을 갱신해 나간다.
3. 모든 과목에 대해 공부시간에 따라 얻을 수 있는 점수의 최댓값을 계산했다면, 모든 공부시간을 비교해 얼마나 공부했을 때 점수를 최대로 얻을 수 있는지 계산한다.

 

 

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include <cmath>
#include <queue>
#include <map>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	int N,T;
	cin >> N>>T;
	vector<int> ti(T + 1, -1);
	ti[0] = 0;
	int dt, sc;
	for (int i = 0; i < N; i++) {
		cin >> dt >> sc;
		for (int j = T; j >= 0; j--) {
			if (ti[j] != -1&&j+dt<=T) {
				ti[j + dt] = max(ti[j + dt], ti[j] + sc);
			}
		}
	}
	int ans = 0;
	for (int i = 0; i <= T; i++) {
		ans = max(ans, ti[i]);
	}
	cout << ans;
	return 0;
}

---

 

비슷한 유형을 접한 적이 있어 쉽게 풀 수 있는 문제였다.

얻을 수 있는 점수의 범위가  100*1000이고, 시간은 10,000이라 기준을 시간으로 했다.

만약 얻을 수 있는 점수의 범위가 더 작았다면, 배열의 크기를 얻을 수 있는 점수로 하고 저장되는 값을 공부 시간으로 풀었을 듯 하다

 

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