구름톤 3주차 후기 - 1

다이나믹 프로그래밍을 이용해서 구현했다.

 

dp[i] = i의 통증을 0으로 만드는 데 필요한 최소 아이템의 개수 라고 정의하면,

i의 통증이 생긴 경우는 i-A의 통증에 A 가 더해진 경우, i - B의 통증에 B 가 더해진 경우를 제외하고는 고칠 수가 없다.

다르게 말하면 i의 통증은 A의 아이템을 써서 i- A 의 통증으로 가라앉을 수 있고, B 아이템을 써서 i - B의 통증으로 가라앉을 수 있다.\

그 외에 해당하는 통증은 해결 될 수 없다. 

 

0통증을 해결하는 최소 아이템 개수 = 0이고, 

이후에 [A] 통증을 해결하면 0 + 1, [B] 통증을 해결하는데  [0] + 1 개의 아이템이 필요하다.

쭉쭉쭉 가서 ... (i) 의 통증을 해결하는 개수는 (i-A) 의 통증을 해결하는데 필요한 개수 + 1 또는 (i-B)의 통증을 해결하는데 필요한 개수 +1 개이다. 

 

dp[i] = dp[i- A] + 1 or dp[i - B]

 

통증을 증가시켜가면서 그 이전의 통증의 최소 개수에 대해 만들 수 있는 통증이라면 + 1을 하면서 업데이트를 해준다.

이때 A, B 아이템을 둘다 써서 도달할 수 있는 경우, 둘 중 최솟값을 이용해서 업데이트를 해준다. 

그 부분이 temp = min(dp[i-A], dp[i-B) 이다. 

 

그 위의 if (i < A) ,else if (i < B).  부분은 범위로 인해서 추가해준 조건일 뿐이다. 

 

구현 코드는 다음과 같다. 

 

 

 

#include <iostream>
using namespace std;
long long N, A, B;
long long dp[1000001] = {0,};
#define INF 2147483646
//2 7 9 11 16

//[a], [b] , [a + b], [a+a], [b+b] .... 
void swap(long long &a, long long &b)
{
	long long temp = a;
	a = b;
	b = temp;
}

int main() {
	cin >> N ;
	cin >> A >> B;
	
	for(int i = 0; i <= N;  i++)
			dp[i] = INF;
	
	dp[0] = 0;
	
	long long temp;
	for(int i = 1; i <= N; i++){
		if(i < A)
			continue;
		else if(i < B)
			temp = dp[i-A];
		else
			temp = min(dp[i-A], dp[i-B]);
		if(temp == INF)
				continue;
		dp[i] = temp + 1;
	}

	if(dp[N] == INF)
			cout << "-1";	
	else
		cout << dp[N];
	//dp[n]  = n 통증을 줄일 수 있는 가장 작은 횟수
	//dp[i] = dp[i-A] + 1 or dp[i-B] + 1. 
	

	
	
	
}