알고리즘 문제풀이/백준
[백준 14888] 연산자 끼워넣기(JAVA/C++)
소보루:-)
2020. 3. 12. 23:00
https://www.acmicpc.net/problem/14888
14888번: 연산자 끼워넣기
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.
www.acmicpc.net
재귀로 값을 계산해서 계속 넘겨주면서 풀면 되는 문제이다.
[JAVA]
import java.util.Scanner;
public class Main {
static int N;
static long min=Long.MAX_VALUE;
static long max=Long.MIN_VALUE;
static int[] num;
static int[] op;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
N=sc.nextInt();
num=new int[N];
op=new int[4];
for(int i=0; i<N; i++) {
num[i]=sc.nextInt();
}
for(int i=0; i<4; i++) {
op[i]=sc.nextInt();
}
for(int i=0; i<4; i++) {
if(op[i]==0)continue;
op[i]--;
dfs(num[0],i,1);
op[i]++;
}
System.out.print(max+"\n"+min);
}
private static void dfs(long sum, int oi,int index) {
if(oi==0) sum+=num[index];
else if(oi==1) sum-=num[index];
else if(oi==2) sum*=num[index];
else if(oi==3) sum/=num[index];
if(index==N-1) {
if(sum<min)min=sum;
if(sum>max)max=sum;
return;
}
for(int i=0; i<4; i++) {
if(op[i]==0)continue;
op[i]--;
dfs(sum,i,index+1);
op[i]++;
}
}
}
[C++]
#include <iostream>
using namespace std;
int N, minVal=1000000000, maxVal=-1000000000;
int num[12];
int op[4];
void Solve(int index,int total) {
if (index == N-1) {
if (total > maxVal) maxVal = total;
if (total < minVal) minVal = total;
return;
}
if (op[0]) {
op[0]--;
Solve(index + 1, total + num[index + 1]);
op[0]++;
}
if (op[1]) {
op[1]--;
Solve(index + 1, total - num[index + 1]);
op[1]++;
}
if (op[2]) {
op[2]--;
Solve(index + 1, total * num[index + 1]);
op[2]++;
}
if (op[3]) {
op[3]--;
Solve(index + 1, total / num[index + 1]);
op[3]++;
}
}
int main() {
cin >> N;
for (int i = 0; i < N; i++)
cin >> num[i];
for (int i = 0; i < 4; i++)
cin >> op[i];
Solve(0,num[0]);
cout << maxVal << endl << minVal;
return 0;
}