[백준/C++] 14728 벼락치기

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

문제에서 주어지는 것을 파악해봤을 때, 배낭 문제와 동일하다는 것을 알 수 있었습니다.


1) 총 시간이 1에서 10000사이의 숫자

2)단원의 개수는 1에서 100 사이의 숫자입니다.

3) 공부시간과 문제의 배점은 1에서부터 1000사이의 숫자입니다.

위의 조건대로 본다면? 이중 for문으로 해결해도 상관이 없고, 자료형도 int로 만들어도 상관이 없습니다. 그래서 내가 갖고있는 시간만큼에서 최대의 점수를 낼 수 있어야 하고, 이 문제의 형식은 배낭문제와 동일합니다.

---

오늘 배낭문제를 다시 이해를 하게 되었습니다.

일단 제가 이해한 방식을 이렇습니다.

해당 문제는 모든 경우의 수를 따져서 제한된 시간안에 최대의 스코어를 얻는 문제입니다.
그렇지만 N의 개수가 100이기 때문에 시간초과가 발생할 수 밖에 없습니다.

이 문제는 Dynamic Programming으로 풀어야합니다. 길게 늘어 쓰니까 꽤나 멋지네요.

그래서, 제 생각은 이러합니다.

해당 과목의 시간(time)과 점수(score)가  1부터 내가 가능한 시간(t)까지 순환하며 비교하는 중에 만약 해당 과목의 시간이 내가 갖고있는 시간내에 처리할 수 있다면? 즉, 순환중인 시간(숫자)내에 처리할 수 있다면?
이전 과목에 해당하는 값과 이전 과목에 해당하는 시간에서 해당 과목의 시간을 제외한 값을 비교한다. 비교해서 더 큰 점수를 갖은 값을 저장한다. 순차적으로 1부터 t까지 해당 과목을 전체 살폈을때 가장 큰 점수가 나올 수 있다.

현재 과목과 현재 시간은 max((이전 과목, 현재시간),(이전 과목, 현재시간 - 현재 강의 시간) + 현재 강의 점수) 가 되겠다.

로 정리할 수 있습니다. 이렇게 차근차근 생각해보면 문제를 해결할 수 있습니다. 물론 저는 배낭문제를 공부하고 문제를 해결했습니다. DP문제를 요즘 천천히 건들고 있는데 항상 어렵네요. 이제서야 골드5로 올라왔습니다.

하지만 다른 구현 문제 또는 알고리즘과는 다르게 재미있는 부분이 여럿 많네요.. 쉬운것도 1시간을 고민하게 만들거나 어려운것도 방식을 빠르게 찾아낸다면 쉽게 풀리는 것처럼 이러한 사고력과 규칙찾기는 훈련이 필요한것 같습니다.

앞으로도 차근차근 해나가야 될것같습니다.

#include<iostream>

using namespace std;

int n,t,time[101], score[101], dp[101][10001];

int main() {
	
	cin >> n >> t;
	
	for(int i = 1; i <= n; i++){
		cin >> time[i] >> score[i];
	}
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= t; j++){
			
			if(j - time[i] >= 0){
				dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - time[i]] + score[i]);
			} else{
				dp[i][j] = dp[i - 1][j];
			}
			
		}
	}

	cout << dp[n][t];
	
	return 0;
}