[백준#C++] 연산자 끼워넣기

1732 단어 DFS재귀백준DFS

문제

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

접근 과정

  1. 조건에 맞게 각각 DFS

코드

#include <iostream>
#include <algorithm>
using namespace std;
 
int n;
int a[13];
int cal[4];
long long min_ans = 1000000000;
long long max_ans = -1000000000;
 
void input(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
    for(int i=0; i<4; i++){   
       cin>>cal[i];
    }
}
 
void dfs(int depth, int plus, int minus, int multi, int div, int res){
	if( depth == n){
		if (max_ans < res) max_ans = res; 
		if (min_ans > res) min_ans = res; 
		return;
	}
 
	if (plus > 0) dfs( depth + 1, plus - 1, minus, multi, div, res + a[depth]);
	if (minus > 0) dfs( depth + 1, plus, minus - 1, multi, div, res - a[depth]);
	if (multi > 0) dfs( depth + 1, plus, minus, multi - 1, div, res * a[depth]);
	if (div > 0) dfs( depth + 1, plus, minus, multi, div - 1, res / a[depth]);
}
 
int main() {
	input();
 
	dfs(1 , cal[0], cal[1], cal[2], cal[3], a[0]);
 
    cout<<max_ans<<"\n";
    cout<<min_ans<<"\n";
	return 0;
}

좋은 웹페이지 즐겨찾기