백트래킹 - 백준 14888번 연산자 끼워넣기

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

IDEA

숫자들 사이에 어떤 기호가 들어갈지 백트랙킹으로 구현하는 문제인 거 같다. 

• 연산자를 해당 숫자 (0 ~3) 으로 cal이라는 배열에 저장
  연산자가 1 0 2 1 식으로 주어진다.
  인덱스 번호에 맞춰 cal 이라는 연산자 배열에 해당 횟수만큼 저장한다. 0 2 2 3 이렇게 cal에 들어간다. 
  
  
• cal 인덱스로 순열을 구현한다.
  숫자가 n개면 연산자는 n-1개이므로 n-1개에 대해서 구현이 끝났으면 check로 넘겨준다.
  
  
• check에서는 연산자 순열에 따라서 숫자들을 계산한다.
  순열이 0 3 2 2 이런 식으로 구성된다면 0은 + , 1은 - , 2는 * , 3은 / 에 맞춰 계산 한 후 
  여태까지 나온 값들 중 최소/최대인지 비교해 저장한다. 

CODE

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

int num[12];
bool visited[12];
vector<int>cal;
vector<int>temp;
int n,m;
long long nmin = 100000000, nmax = -1000000000;

void check() {
	long long answer = num[0];
	for (int i = 0; i < temp.size(); i++) {
		if (temp[i] == 0) answer += num[i + 1];
		else if (temp[i] == 1) answer -= num[i + 1];
		else if (temp[i] == 2) answer *= num[i + 1];
		else answer /= num[i + 1];
	}
	nmin = min(nmin, answer);
	nmax = max(nmax, answer);
	return;
}

//n-1Pn-1 순열 구현 
void dfs(int cnt) {
	if (cnt == n - 1) {
		check();
		return;
	}
	for (int i = 0; i < cal.size(); i++) {
		if (visited[i]) continue;
		visited[i] = true;
		temp.push_back(cal[i]);
		dfs(cnt + 1);
		temp.pop_back();
		visited[i] = false;
	}
}

int main(){
	scanf("%d ", &n);
	for (int i = 0; i < n; i++) scanf("%d", &num[i]);
	//연산자 + = 0 , - = 1 , * = 2 , /=3;
	for (int i = 0; i < 4; i++) {
		int ope;
		scanf("%d", &ope);
		for (int j = 0; j < ope; j++) {
			cal.push_back(i);
		}
	}
	dfs(0);
	printf("%lld\n%lld" ,nmax, nmin);
}                                  

 

남의 CODE

백트랙킹 문제에 대해서 더 연습이 필요할 거 같다.......백트래킹에서 자신있는게 순열과 조합밖에 없어서인지 자꾸 이거에 의존하게 된다.... 

 

사칙연산에 대해서 operators라는 배열을 만들어 각 연산의 횟수를 저장한다. 

findAnswer라는 함수에서 사칙연산 4개 모두에 대해 재귀함수를 사용한다. 

1 0 2 1 과 같이 0 즉, 특정연산이 한 번도 사용되지 않는 경우가 있기에 0보다 클 때만 실행하게 만들어놓았다.

operator[i] 의 연산을 시행할테니 하나 빼준 후 재귀가 끝나면 다시 하나 더해주어 돌려준다. 

 

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

int n, minResult = 987654321, maxResult = -987654321;
int digit[12];
int operators[4];


void findAnswer(int d, int idx)
{
    if (idx == n)
    {
        if (d > maxResult)
            maxResult = d;
        if (d < minResult)
            minResult = d;
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        if (operators[i] > 0)
        {
            operators[i]--;
            if (i == 0)
                findAnswer(d + digit[idx], idx + 1);
            else if (i == 1)
                findAnswer(d - digit[idx], idx + 1);
            else if (i == 2)
                findAnswer(d * digit[idx], idx + 1);
            else
                findAnswer(d / digit[idx], idx + 1);
            operators[i]++;
        }
    }
    return;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> digit[i];
	for (int i = 0; i < 4; i++)
			cin >> operators[i];
	findAnswer(digit[0], 1);
	cout <<  maxResult << "\n" << minResult;
	return 0;
}

흐ㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜ백트래킹 너무 어렵다 연습이 더 필요할 거 같다. 😢😢