SWEA 4008번 [모의 SW 역량테스트] 숫자 만들기 C++ DFS, 백트래킹

리뷰

처음엔 최악의 케이스만 생각하여 시간내에 가능 할까? 라는 생각이 들었는데 생각보다 여유롭게 풀렸다.

백트래킹이나 DFS는 생각이 너무 많아지면 더 어려운 문제인 것 같다.

 

문제 풀이

1. 각 테스크 케이스 마다 min_val은 아주 큰 값으로, max_val은 아주 작은 값으로 초기화를 해준다.
2. 숫자의 개수와 부호의 개수를 각각 받아와 주고 각 숫자를 배열에 입력 받아준다.
3. 재귀의 깊이를 나타낼 level과 연산에 사용할 숫자를 매개변수로 백트래킹을 통해 완전 탐색을 실행해준다.
4. 모든 완전 탐색을 마친 뒤 각 테스트 케이스마다 max_val - min_val 값을 출력해 주면 된다.

 

참고 사항

dfs 함수 정보

1. 기저 조건 : level이 n - 1에 도달했을 경우 max_val과 min_val을 최신화
2. 반복문 : 연산자의 개수는 총 4개이므로 4번의 반복문을 실행
3. 판별식 : if (op[i]) 만약 현재 연산자가 사용 가능한지를 판별
4. 재귀 이전 : 판별식이 참인 경우이므로 op[i]의 개수를 1개 빼준다.
5. 재귀 : level + 1, 각 연산자에 맞는 연산을 val과 다음 숫자를 통해 연산해 준 값을 재귀 처리 해준다.
6. 재귀 후 : 재귀 이전 빼주었던 op[i]의 개수를 1개 더해주어 원상 복구 해준다.

 

정답 코드

#include<iostream>

using namespace std;

int tc, n, min_val, max_val;
int op[4];
int nums[13];

void dfs(int level, int val) {
	if (level == n - 1) {
		max_val = max(max_val, val);
		min_val = min(min_val, val);
		return;
	}

	for (int i = 0; i < 4; i++) {
		if (op[i]) {
			op[i]--;
			if (i == 0) dfs(level + 1, val + nums[level + 1]);
			if (i == 1) dfs(level + 1, val - nums[level + 1]);
			if (i == 2) dfs(level + 1, val * nums[level + 1]);
			if (i == 3) dfs(level + 1, val / nums[level + 1]);
			op[i]++;
		}
	}
}

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

	cin >> tc;
	for (int c = 1; c <= tc; c++) {
		min_val = 999999999, max_val = -999999999;
		cin >> n >> op[0] >> op[1] >> op[2] >> op[3];
		for (int i = 0; i < n; i++) cin >> nums[i];
		dfs(0, nums[0]);
		cout << "#" << c << " " << max_val - min_val << "\n";
	}
}