SWEA 1952번 [모의 SW 역량테스트] 수영장 C++ 백트래킹

리뷰1

굉장히 쉬운 백트래킹 문제, 정답률이 67%인 이유가 있는듯 하다.

 

문제 풀이

1. 각 테케마다 최소값을 비교할 mp 변수를 5억정도의 큰 크기로 초기화 해준다.
2. 1일권, 1달권, 3달권, 1년권의 가격을 모두 받아오고, 1년간 월별 수영장을 사용할 일수를 받아온다.
3. level과 price가 0인 채로 dfs를 실행해 주고, 4개의 이용권을 각각 사용하는 경우의 수를 완전탐색 돌려준다.
4. 기저조건에 도달했다면 mp와 비교하여 최소값을 갱신해 주고, 각 테스트 케이스마다 mp값을 출력해 준다.

 

참고 사항

dfs함수의 내부구조는 다음과 같다.

1. 매개변수로는 level과 price를 사용해 준다. level은 개월 수를 나타내줄 것이고 price는 누적 값을 나타낸다.
2. 기저조건으로 level이 12 이상일때 즉, 1년이 지났을때 mp의 최소값을 갱신해 주고 리턴한다.
3. 또한, 현재 mp가 이미 price보다 적을 경우에는 더 이상 탐색할 필요가 없으니 리턴한다.
4. 판별조건은 따로 없으며 그냥 네개의 티켓 구매한 경우를 매개변수를 적절히 전달하여 재귀를 돌려주면 된다.

 

정답 코드

#include<iostream>

using namespace std;

int tc, mp;
int e[4];
int m[12];

void dfs(int level, int price) {
	if (level >= 12) {
		mp = min(mp, price);
		return;
	}
	if (mp <= price) return;
	for (int i = 0; i < 4; i++) {
		if (i == 0) dfs(level + 1, price + e[0] * m[level]);
		if (i == 1) dfs(level + 1, price + e[1]);
		if (i == 2) dfs(level + 3, price + e[2]);
		if (i == 3) dfs(level + 12, price + e[3]);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> tc;
	for (int c = 1; c <= tc; c++) {
		mp = 500000000;
		cin >> e[0] >> e[1] >> e[2] >> e[3];
		for (int i = 0; i < 12; i++) cin >> m[i];
		dfs(0, 0);
		cout << "#" << c << " " << mp << "\n";
	}
}