40. UVa-10576 Y2K Accounting Bug

문제

<그림1: 문제 설명>

문제요약:

말이 조금 어려워서 이해하기 힘들 수 있다. 문제에 필요한 정보만 써보면 다음과 같다.

Input으로는 차례대로 s와 d가 주어지는데 각각은 이득, 손해를 의미하는 변수다. 그리고 이 회사의 열두달 동안 어떤 달에 이득을 봤다면 무조건 그 달에는 +s만큼 이득을 본 것이고, 손해를 봤다면 -d만큼 손해를 본 것이다.

즉 어떤 달의 earning은 +s 혹은 -d일 수밖에 없다. 

이 때 5월부터는 해당 월을 포함한 지난 다섯 달의 earning을 합친 report를 작성할 수 있다. 이 때 5월부터 12월까지 총 8개의 report를 작성할 수 있는데 이 회사의 모든 8개의 report는 음수여야 한다.

이런 조건을 만족하는 1년의 손해/이익표를 생각해볼 수 있을 것이다. 이 때 손익표에서 일 년 동안의 +s와 -d를 모두 더한 sum을 생각할 때 sum이 양수가 나올 수 있다면 그 값들 중 최댓값을 출력하고 양수가 불가능한 조건이면 Deficit을 출력하라

 

문제 풀이는 recursive backtracking으로 했다. 슬슬 이 방법에 대해서도 감이 잡히는 것 같다. 코드는 다음과 같다.

 

#include<iostream>
using namespace std;
int s, d;
//s: getting
//d: losing

int Month_earning[12];	//달에 얻은 금액을 메모하는 배열
int maxsum;
void backTracking(int c, int sum) {
	// c: 몇번째 달까지 봤는가?(0~11) 
	// sum: 현재까지 총 이득과 적자를 더한 sum
	if (c < 4) {//report는 5월부터 갱신된다.
		Month_earning[c] = s;
		backTracking(c + 1, sum + s);
		Month_earning[c] = -d;
		backTracking(c + 1, sum - d);
	} //이때는 report를 생각할 필요 없음
	else if (c == 12) { // 다 보고 온 경우(report조건을 만족하면서 complete case를 완성한 경우)
		if (maxsum < sum) {
			maxsum = sum;
		}
	}
	else {	//기본 case c=4~11
		int report;
		//가지치기->report값의 평가로 그 값이 양수면 더이상 진행할 필요가 없다.
		Month_earning[c] = s;
		report= Month_earning[c] + Month_earning[c - 1] + Month_earning[c - 2] + Month_earning[c - 3] + Month_earning[c - 4];
		if(report<0) backTracking(c + 1, sum + s);
		Month_earning[c] = -d;
		report = Month_earning[c] + Month_earning[c - 1] + Month_earning[c - 2] + Month_earning[c - 3] + Month_earning[c - 4];
		if(report<0) backTracking(c + 1, sum - d);
	}
}




int main() {
	while (cin >> s >> d) {
		maxsum = 0;
		backTracking(0, 0);
		if (maxsum == 0) cout << "Deficit" << endl;	//0원이득이나 손해를 본 경우 전부 DEFECIT
		else cout << maxsum << endl;
	}



}

어려운 문제는 아닌 것 같다.