[SWExpertAcademy] 1952번 수영장 C++

문제 : 1년 동안 각 달의 수영장 이용 계획을 세우고 가장 적은 비용으로 수영장을 이용할 수 있는 방법 찾기

<수영장 이용권>

1. 1일 이용권 : 하루 이용 가능.

2. 1달 이용권 : 한 달 이용 가능. 매달 1일부터 시작.

3. 3달 이용권 : 연속 세 달 이용 가능. 매달 1일부터 시작. (11월, 12월, 다음해 1월 사용 불가능)

4. 1년 이용권 : 일 년 이용 가능. 매년 1월 1일부터 시작.

 

- 입력

테스트 케이스 T

    1일 이용권 요금, 1달 이용권 요금, 3달 이용권 요금, 1년 이용권 요금

    1월~12월 이용 계획

 

- 출력

수용장 이용 계획대로 진행했을 때 가장 적게 지출하는 비용

 

- 제약 사항

10 ≤ 이용권 요금 ≤ 3,000

각 달의 이용 계획은 각 달의 마지막 일자보다 크지 않음

---

문제 이해

1월부터 12월까지 달마다 수영장을 이용하는 계획 정보가 있고, 수영장 이용에는 4개의 이용권 종류가 있는데 이들을 조합해서 가장 적은 비용으로 수영장을 이용할 수 있도록 하며, 그 비용을 출력한다!

 

접근 방법

DFS를 사용해서 수영장 이용권과 수영장 이용 계획 정보의 모든 조합을 살핀다.

 

코드

#include <iostream>
#include <cstring>
using namespace std;

int T;
int fee[4];
int plan[12];

int result = 21e8;

void makePlan(int now, int sum) {
	
	if (now >= 12) {
		if (result > sum && sum != 0)
			result = sum;

		return;
	}

	int nowTimes = plan[now];
	if (nowTimes == 0) {
		makePlan(now + 1, sum);
	}

	for (int i = 0; i < 4; i++) {

		int nowFee = fee[i];

		if (i == 0) {
			makePlan(now + 1, sum + (nowTimes * nowFee));
		}
		else if (i == 1) {
			makePlan(now + 1, sum + nowFee);
		}
		else if (i == 2) {
			makePlan(now + 3, sum + nowFee);
		}
		else {
			makePlan(now + 12, sum + nowFee);
		}
		
	}


}

int main() {
	
	cin >> T;

	for (int t = 1; t <= T; t++) {
		for (int i = 0; i < 4; i++) cin >> fee[i];
		for (int i = 0; i < 12; i++) cin >> plan[i];
		
		makePlan(0, 0);

		cout << '#' << t << ' ' << result << endl;
		result = 21e8;
	}

}

1월부터 12월까지 재귀를 돌려서 해당 달에 이용할 이용권을 4개 중에 하나 선택하도록 for 반복문을 4개 돌린다. 이 4개 중 하나를 택해서 해당 이용권을 사용하게 되면 지불해야하는 금액을 sum에 더한 뒤에 다음 달로 넘기도록 구현하였다.