반응형
N의 범위를 확인해본 결과 11이므로 nextPermutation()또는 백트래킹을 이용한 순열을 사용하는 문제이다.
하지만 이문제에서 주의할점은 순열을 구해하는 수,기호 에는 중복이 되는 것이 있으므로 무조건 nextPermutation()을 직접 구현해야 풀 수 있는 문제이다. 연산자들을 모아놓은 op배열을 생성후 모든 number에 대하여 연산을 해주면 쉽게 풀어지는 문제이다. 관건은 nextPermutation()의 직접 구현이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
package online.base;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main_bj_14888_연산자끼워넣기 {
static int N, totalOp;
static int[] numbers;
static int[] op;
static int max,min;
public static void main(String[] args) throws Exception {
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N=Integer.parseInt(br.readLine());
numbers=new int[N];
st=new StringTokenizer(br.readLine());
for(int i=0;i<N;i++)
numbers[i]=Integer.parseInt(st.nextToken());
totalOp=N-1;
op=new int[totalOp];
st=new StringTokenizer(br.readLine());
int index=0;
for(int i=0;i<4;i++) {
int count=Integer.parseInt(st.nextToken());
for(int j=0;j<count;j++)
op[index++]=i;
}
max=Integer.MIN_VALUE;
min=Integer.MAX_VALUE;
calc();
System.out.println(max);
System.out.println(min);
}
static void calc() {
do {
int sum=numbers[0];
for(int i=0;i<N-1;i++) {
if(op[i]==0) {
sum+=numbers[i+1];
}else if(op[i]==1) {
sum-=numbers[i+1];
}else if(op[i]==2) {
sum*=numbers[i+1];
}else if(op[i]==3) {
sum/=numbers[i+1];
}
}
if(sum>max)
max=sum;
if(sum<min)
min=sum;
}while(nextPermutation());
}
static boolean nextPermutation() {
int i=totalOp-1;
//1.등호가 < 되는 곳 찾기
while(i>0 && op[i-1]>=op[i] )
i--;
if(i==0)
return false;
//2.arr[i-1]보다 큰 arr[j] 찾기
int j=totalOp-1;
while(op[i-1]>=op[j])
j--;
//3.arr[i-1], arr[j] 교환
int temp = op[i-1];
op[i-1]=op[j];
op[j]=temp;
int k=totalOp-1;
//4.i부터 N-1까지 오름차순으로 교환
while(i<k) {
temp=op[i];
op[i]=op[k];
op[k]=temp;
i++;k--;
}
return true;
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
반응형
'Algorithm' 카테고리의 다른 글
[BOJ] 1753. 최단경로 (0) | 2020.04.12 |
---|---|
[BOJ] 1922. 네트워크 연결 (0) | 2020.04.12 |
[BOJ] 1197. 최소 스패닝 트리 (0) | 2020.04.09 |
[SWEA] 1251. 하나로 (0) | 2020.04.09 |
[BOJ] 10971. 외판원 순회2 (0) | 2020.04.08 |