Algorithm

[BOJ] 14888. 연산자 끼워넣기

프로그래민 2020. 4. 9. 22:22
반응형

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;
 
 
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