Dynamic Programming - Select Working Days

Select Working Days

• 배열에는 그날 벌 수 있는 돈들이 저장.
• 최대로 일해서 벌수있는 돈의 총합 구하기.
• 연속으로 일하는 것은 불가능.

순서 정하기 : 첫째날부터 x날까지 순서대로.
(뒤쪽의 일이 앞쪽의 일에 영향을 주지 않기 때문에 순서를 이렇게 정할 수 있다.)

a[x] : x일에 벌 수 있는 돈
D[x] : x일 까지 최대로 많이 벌 수 있는 돈의 총합.

집합 나누기 : D[x] 는 다음과 같이 쪼갤 수 있다.
1. x일에 일하는 경우
⇒ 연속으로 일하면 안되므로 D[x-1]에서 일하지 않는 경우 + a[x]
2. x일에 일하지 않는 경우
⇒ D[x-1]에서 일하는 경우 혹은 일하지 않는 경우에서 최댓값이 답

이 두 케이스중 최대가 D[x] 이다.
그리고 D[x]에서 일하는 경우는 D[x][1]에 저장되고
D[x]에서 일하지 않는 경우는 D[x][0]에 저장된다.

int W(int a[], int n)
{
	int D[n+1][2];
	D[1][0] = 0;
	D[1][1] = a[1];

	for(i=2; i<=n; i++)
	{
		D[i][0] = Max(D[i-1][0], D[i-1][1]); // i일에 일하지 않는 경우
		D[i][1] = D[i-1][0] + a[i]; // i일에 일하는 경우
	}
	
	return Max(D[n][0], D[n][1]);
}