[SWEA] 수영장 (C++, 삼성 기출)

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?contestProbId=AV5PpFQaAQMDFAUq&solveclubId=AV6kld8aisgDFASb&problemBoxTitle=%EC%82%BC%EC%84%B1+%EC%8B%A0%EC%9E%85+%EB%AA%A8%EC%9D%98+sw+%EC%97%AD%EB%9F%89%ED%85%8C%EC%8A%A4%ED%8A%B8+%EB%AC%B8%EC%A0%9C%EB%AA%A8%EC%9D%8C&problemBoxCnt=10&probBoxId=AV732SG66sEDFAW7

삼성 코테가 얼마 안남아서 SWEA 문제들을 풀고 있다.
이 문제는 재귀 + 완전탐색으로 해결했다.
모든 경우를 다 비교해가면서 sum 값을 갱신시키고, 가장 작은 값을 넣어주는 것이다.

if (idx >= 12) {
		answer = min(sum, answer);
		return;
	}
	if (sum > answer) return;
	if (month[idx] == 0) solve(idx + 1, sum, fee, month);
	else {
		solve(idx + 1, sum + fee[0] * month[idx], fee, month);
		solve(idx + 1, sum + fee[1], fee, month);
		solve(idx + 3, sum + fee[2], fee, month);
		solve(idx + 12, sum + fee[3], fee, month);
	}

메인 알고리즘이다.
12월이 지나면 answer를 갱신해주고 return 해준다.
sum이 answer보다 큰 경우는 고려해줄 필요가 없으므로 return 해준다.
그 이외의 경우는 month == 0일 때에도 고려하지 않아도 되고, 1일, 1달, 3달, 1년 사용권을 고려해 계산해주면 된다.

전체 코드

#include <iostream>
#include <vector>

using namespace std;

int answer;

void solve(int idx, int sum, vector<int> fee, vector<int> month) {
	if (idx >= 12) {
		answer = min(sum, answer);
		return;
	}
	if (sum > answer) return;
	if (month[idx] == 0) solve(idx + 1, sum, fee, month);
	else {
		solve(idx + 1, sum + fee[0] * month[idx], fee, month);
		solve(idx + 1, sum + fee[1], fee, month);
		solve(idx + 3, sum + fee[2], fee, month);
		solve(idx + 12, sum + fee[3], fee, month);
	}
}

int main(int argc, char** argv)
{
	int test_case;
	int T;

	cin >> T;

	for (test_case = 1; test_case <= T; ++test_case)
	{
		answer = 987654321;
		vector<int> fee(4);
		vector<int> month(12);
		for (int i = 0; i < 4; i++) cin >> fee[i];
		for (int i = 0; i < 12; i++) cin >> month[i];
		solve(0, 0, fee, month);
		cout << "#" << test_case << " " << answer << "\n";
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}