백준 14888. 연산자 끼워넣기(순서 상관없는 순열)

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

들어온 연산자(+ + - x /)를 순서 상관없이 나열하는 것을 구현하는 게 핵심이다. 

이를 위해 나는 백트래킹을 사용했지만, next_permutation을 사용하면 훨씬 간단하게 구현할 수 있을 것같다. 

문제를 풀고 next_permutation을 다시 공부했는데, next_permutation이 순서 상관없는 순열이었다. 순서 상관 있는 순열인줄.... 그래서 그냥 이문제는 next_permutation을 쓰면 금방 풀리는 문제이다.

비슷한 문제로 백준 15663. N과 M (9)을 풀어보면 좋을 거같다. 

 

1. 특징

1) 같은 것이 있는 순열 (백트래킹 or next_permutation)

 

2. 삽질 포인트

1) 백트래킹: 순서 없는! 순열을 구현하는 게 헷갈렸다. 나는 tmp를 설정하여 이번 배열[cur]에 들어가는 값을 기억하고, i가 증가하여 다시 그 배열[cur]에 이전 값과 같은 값(tmp)이 들어가려한다면, 해당 i를 뛰어넘게 했다. 

이는 순회하고 있는 배열(operarr)가 같은 값들은 연속적이기 때문에 가능하다. ({+-+*/}가 아닌 {++-*/}의 형태이다. 따라서 i를 증가시켜서 해당 값이 이전 값과 연속된 값인지를 판별할 수 있다.)

 

3. 구현 포인트

1) 백트래킹

2) next_permutation: 순서 없는 순열

int mask[3] = {1, 1, 2};
do
{
    for(int i= 0; i < 3; i++)
        cout << mask[i] << ' ';

    cout << '\n';
    
}while(next_permutation(mask, mask+3));

//1 1 2 
//1 2 1 
//2 1 1

 

4-1. 코드 (백트래킹)

#include <string>
#include <iostream>
#include <limits.h>
using namespace std;

int n;
int arr[12];
int operarr[12];
int tmparr[12];
int vis[12];
int mx;
int mn;
int tmval;
void func(int cur)
{
    if(cur == n-1)
    {
        tmval = arr[0];
        for(int i = 1; i < n; i++)
        {
            if(tmparr[i-1] == 0) tmval += arr[i];
            if(tmparr[i-1] == 1) tmval -= arr[i];
            if(tmparr[i-1] == 2) tmval *= arr[i];
            if(tmparr[i-1] == 3) tmval /= arr[i];

        }
        mx = max(mx, tmval);
        mn = min(mn, tmval);
        return;
    }

    int tmp = -1;
    for(int i = 0; i < n-1; i++)
    {
        if(vis[i] == true) continue;
        if(tmp == operarr[i]) continue;
        vis[i] = true;
        tmparr[cur] = operarr[i];
        tmp = operarr[i];
        func(cur+1);
        vis[i] = false;
    }
}

int main()
{
    cin >> n;

    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    int x;
    int cnt = 0;
    for(int i = 0; i < 4; i++)
    {
        cin >> x;
        for(int j = 0; j < x; j++)
            operarr[cnt++] = i;
    }
    
    mx = INT_MIN;
    mn = INT_MAX;

    func(0);
    cout << mx <<'\n';
    cout << mn <<'\n';

}

 

4-2. 코드 (next_permutation)

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

int n;
int arr[12];
int operarr[12];
int mx;
int mn;
int tmval;
int idx;

int main()
{
    cin >> n;

    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    int x;
    int cnt = 0;
    for(int i = 0; i < 4; i++)
    {
        cin >> x;
        for(int j = 0; j < x; j++)
            operarr[cnt++] = i;
    }
    
    mx = INT_MIN;
    mn = INT_MAX;

    do
    {
        tmval = arr[0];
        idx = 1;
        for(int i = 0; i < n-1; i++)
        {
            if(operarr[i] == 0) tmval += arr[idx++];
            if(operarr[i] == 1) tmval -= arr[idx++];
            if(operarr[i] == 2) tmval *= arr[idx++];
            if(operarr[i] == 3) tmval /= arr[idx++];
        }

        mx = max(mx, tmval);
        mn = min(mn, tmval);

    }while(next_permutation(operarr, operarr+n-1));




    cout << mx <<'\n';
    cout << mn <<'\n';

}