백준 Gold 5 벼락치기

벼락치기 (백준 Gold 5)

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

주어지는 문제 N개와 T의 남은 시간을 통해
최소 벌금 금액을 구하는 문제

• 문제는 소요일수 d와 벌금 m으로 이루어져 N개 주어짐
  

풀이 방법

점화식

• dp[i] : dp[i] 일자에서 내야하는 최소 벌금
  
  • 배낭 문제이지만, ‘이전 상태’만을 알면 되기에
    1차원으로 풀 수 있다고 판단하였다
    

다음 상태 이동

• dp[j] = min(dp[j], dp[j - nowT] - nowV)
  
  • 최소 dp이기에 초기값을 ‘MaxV’로 설정
    
  • 또한 Min 과 - 연산
    

순회 방식

• 1차원이며, 최종 t값을 각 문제마다 1번만 갱신해야 하기에
  t -> nowTime 으로 갱신
  
  • 해당 문제를 풀 수 있는 날자들 중
    가장 작은 값으로 갱신하는 방식
    

제출 코드

#include<iostream>
#include<vector>

using namespace std;

int main()
{
	int n, t;
	cin >> n >> t;

	int maxV = 0;
	vector<int> vals, times;
	for (int i = 0; i < n; i++)
	{
		int d, m;
		cin >> d >> m;
		times.push_back(d);
		vals.push_back(m);
		maxV += m;
	}

	// dp[i] : i번째 일에서 가장 작은 수치의 값
	vector<int> dp(t + 1, maxV);
	
	for (int i = 0; i < n; i++)
	{
		int nowV = vals[i];
		int nowT = times[i];

		for (int j = t; j >= nowT; j--)
		{
			dp[j] = min(dp[j], dp[j - nowT] - nowV);
		}
	}

	cout << dp[t];

	return 0;
}

결과

배낭 문제를 비교적 가볍게 푸는 방식은 조금 익숙해진 듯하다