[백준]연산자끼워넣기(두번째풂)

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

14888번: 연산자 끼워넣기

두번째 풀었는데 이번엔 15분 컷이었다.

연산자들을 순열로 배열하면 된다고 생각했고, dfs+백트래킹으로 만들면 된다고 생각했다.

요즘 dfs코딩하다가 느낀건데 전역변수로 두고 dfs를 진행해주면 다음에 진행될때 반드시 초기화된

정보를 가지고 해주어야된다는것이고, 아니면 파라미터로 가져가서 그 변수를 계속 이용해주어야 한다는것을 알았다.

그리고 명확한 마지막 N을 정해서 return문을 정해주는 dfs --> 파라미터를 통해 해당 len이 되면 종료하는 방식-->

(선택만 하면서 true로 바꾸고 실행 false로 바꾸는 형태)에서 선택된 N개의 데이터로 문제를 처리하는 방식

그리고 해당 문제와 같이 누적해가면서 바로바로 파라미터값을 바꾸면서 실행해주는 방식이 있다는 것을 알았다.

구분을 해 줄 필요가 있는것 같다.

 

#include <iostream>
using namespace std;
 
/*1. + , - , X , % 쁠마곱나 순
2.dfs로 순열처리 ##dfs를 할때 하나씩 개수를 늘려가면서 재보는 경우와 갯수를 주어지는 경우가 있는거같다
3.B배열이 양수이면 조건으로 들어가서 -- ++ 를 해주기.
4.len변수를 만들어서 누적시키는 방식으로 sum계산 len이 N이면 최대최소 저장
5.dfs에서만 변수를 사용하기 위해서는 전역으로 하면 다음실행에서의 초기화를 꼭 해주거나 파라미터로 이어나가야함*/
 
int N;
int A[12];
int B[4]; //+,-,x,%
int min_a=1e9, max_a=-1e9;
 
void dfs(int SUM, int len) {
    if (len == N) { 
        if (SUM >= max_a) max_a = SUM;
        if (SUM <= min_a) min_a = SUM;
        return; 
    }
 
    if (B[0] > 0) {
        B[0]--;
        dfs(SUM + A[len], len + 1);
        B[0]++;
    }
    if (B[1] > 0) {
        B[1]--;
        dfs(SUM - A[len], len + 1);
        B[1]++;
    }
    if (B[2] > 0) {
        B[2]--;
        dfs(SUM*A[len], len + 1);
        B[2]++;
    }
    if (B[3] > 0) {
        B[3]--;
        dfs(SUM / A[len], len + 1);
        B[3]++;
    }
    
}
 
int main()
{    
    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < 4; i++) cin >> B[i];
 
    dfs(A[0], 1);
    printf("%d\n%d\n", max_a, min_a);
 
    return 0;
}