SWEA 4008. 숫자 만들기 (C++)

모옹·2023년 2월 18일
0

알고리즘

목록 보기
7/18

요약

각 연산기호의 개수를 입력받고 나서,
모든 순서를 인덱스를 통해서 순열로 만들고
하나하나 계산해보면서 Max, Min값 기록해서 계산하자


문제

N개의 숫자가 적혀 있는 게임 판이 있고,
+, -, x, / 의 연산자 카드를 숫자 사이에 끼워 넣어 다양한 결과 값을 구해보기로 했다.
수식을 계산할 때 연산자의 우선 순위는 고려하지 않고 왼쪽에서 오른쪽으로 차례대로 계산한다.

주어진 연산자 카드를 사용하여 수식을 계산했을 때
그 결과가 최대가 되는 수식과 최소가 되는 수식을 찾고,
두 값의 차이를 출력하시오.

[제약사항]
1. 시간 제한 : 최대 50 개 테스트 케이스를 모두 통과하는 데 C / C++ / Java 모두 3 초
2. 게임 판에 적힌 숫자의 개수 N 은 3 이상 12 이하의 정수이다. ( 3 ≤ N ≤ 12 )
3. 연산자 카드 개수의 총 합은 항상 N - 1 이다.
4. 게임 판에 적힌 숫자는 1 이상 9 이하의 정수이다.
5. 수식을 완성할 때 각 연산자 카드를 모두 사용해야 한다..
6. 숫자와 숫자 사이에는 연산자가 1 개만 들어가야 한다.
7. 완성된 수식을 계산할 때 연산자의 우선 순위는 고려하지 않고, 왼쪽에서 오른쪽으로 차례대로 계산한다.
8. 나눗셈을 계산 할 때 소수점 이하는 버린다.
9. 입력으로 주어지는 숫자의 순서는 변경할 수 없다.
10. 연산 중의 값은 -100,000,000 이상 100,000,000 이하임이 보장된다.


[입력]
각 테스트 케이스의 첫 번째 줄에는 숫자의 개수 N 이 주어진다.
다음 줄에는 '+', '-', '*', '/' 순서대로 연산자 카드의 개수가 공백을 사이에 두고 주어진다.
다음 줄에는 수식에 들어가는 N 개의 숫자가 순서대로 공백을 사이에 두고 주어진다.

[출력]
정답은 연산자 카드를 사용하여 만들 수 있는 수식으로 얻은 결과값 중
최댓값과 최솟값의 차이이다.

풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
int acc[4];
int map[15];
vector<int>calc;

void DFS(int now, int cnt) {

	if (cnt == N) {
		calc.push_back(now);
		return;
	}

	if (acc[0]) {
		now += map[cnt];
		cnt++;
		acc[0]--;
		DFS(now, cnt);
		acc[0]++;
		cnt--;
		now -= map[cnt];
	}
	if (acc[1]) {
		now -= map[cnt];
		cnt++;
		acc[1]--;
		DFS(now, cnt);
		acc[1]++;
		cnt--;
		now += map[cnt];
	}
	if (acc[2]) {
		now *= map[cnt];
		cnt++;
		acc[2]--;
		DFS(now, cnt);
		acc[2]++;
		cnt--;
		now = now / map[cnt];
	}
	if (acc[3] && map[cnt] != 0) {
		// 나머지를 먼저 계산해둬야함
		int rest = now % map[cnt];
		now = now / map[cnt];
		cnt++;
		acc[3]--;
		DFS(now, cnt);
		cnt--;
		now = now * map[cnt] + rest;
		acc[3]++;
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie();
	cout.tie();

	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {

		calc.clear();

		cin >> N;
		for (int i = 0; i < 4; i++) {
			cin >> acc[i];
		}
		for (int i = 0; i < N; i++) {
			cin >> map[i];
		}

		DFS(map[0], 1);
		sort(calc.begin(), calc.end());
		int ans = calc[calc.size()-1] - calc[0];
		cout << "#" << tc << " " << ans << "\n";
	}
	return 0;
}

0개의 댓글