[백준] 14888번 연산자 끼워넣기 JAVA (자바) 풀이

문제 14888번 

 :  N개의 수열 (A1, ... , AN) 주어진다 
    수 사이에 끼워넣을 수 있는 N-1개의 연산자 (+ 덧셈, - 뺄셈, × 곱셈, ÷ 나눗셈) 주어진다
    숫자 순서 바꿀 수 X, 연산자 순서 바꿀 수 O

 :  우선순위 무시하고 앞에서부터 계산
    나눗셈은 몫만 구하고, 음수를 양수로 나눌 때에는 숫자끼리만 나누고 몫에 -만 붙여준다 (=음수처리)

 :  결과식 최대인 것과 최소인 것을 구해라

 

[입력]

 :  첫 줄에 수열 개수 N

 :  둘째 줄 N개의 수열

 :  연산자 개수 ( +, -, ×, ÷ 순서 )    

[출력]

 :  식 최댓값 첫째줄에, 식 최솟값 둘째줄에 출력

 

 

 [알고리즘]

 

출처 https://adjh54.tistory.com/196

 

1. 모든 경우를 분석해야 하는구나 = 완전 탐색 = 브루트 포스
2. 연산자의 조합을 이용해야 한다 = 순열
3. 순열을 쉽게 구하기 위해서는 백트래킹

   →  이 문제는 백트래킹 문제로 풀어야 한다
   →  재귀를 이용하고 있고 가지치기를 하지 않기 때문에 dfs로 풀었다고 봐도 무방하다

​

• 브루트 포스 (완전탐색) = 모든 가능한 경우를 전부 탐
• 백트래킹 = 탐색을 진행하고 조건에 맞지 않는 부분을 제외하면서 탐색
• DFS = 트리를 완전 탐색하는 한가지 방법, 모든 경로 탐색

 

 [설명 예시]

 

 

<백트래킹 코드 과정>

 

[1] for문 4번 돌기

     이는 각 수열마다 연산자를 모두 돌리기 위함이다

     (예) 수열에서 1과 2 사이에는 연산자 4가지 종류를 모두 넣는다

 

[2] 연산 배열이 0보다 클 때 if문 실행

     1. 연산 배열 하나 줄이기 (연산자를 사용했다는 표시)

 

     2.  switch ~ case 문을 통해 해당 연산자가 무엇인지 파악하고

         연산자를 넣어 계산한 값과 index(계산 횟수)를 다음 백트래킹에 대입

 

     3. 연산 배열 다시 ++ (여러 경우의 수 계산을 위해 다시 사용하려고 ++)
         이때 중요한 것은 2번 과정에서 하위 백트래킹과정까지 모두 마친 뒤에 실행한다

 

[3] index = N 일 경우 max와 min을 갱신해서 여러 경우의 수를 비교한다

 

 

(예시) for문에서 i = 0인 경우

 [코드]

import java.util.*;
import java.io.*;
public class Main{
    static int N;
    static int arr[];
    static int cal[] = new int[4];
    static int max = Integer.MIN_VALUE;    
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());        
        }
         st = new StringTokenizer(br.readLine());
        for(int j=0;j<4;j++){
            cal[j] = Integer.parseInt(st.nextToken());
        }
        Back(arr[0],1);
        System.out.println(max);
        System.out.println(min);
    }
    
    public static void Back(int step, int index){
        if(index == N){
            max = Math.max(max,step);
            min = Math.min(min,step);
            return;
        }
        for(int i=0; i<4; i++){
            if(cal[i]>0){
                cal[i]--;
            
                switch(i){
                    case 0:
                        Back(step + arr[index], index+1);
                        break;
                 
                    case 1:
                        Back(step - arr[index], index+1);
                        break;
                        
                    case 2:
                        Back(step * arr[index], index+1);
                        break;
                    
                    case 3:
                        Back(step / arr[index], index+1);
                        break;
                }
                cal[i]++;
            }
       
        }
       
    }
}

 

 

 [해설]
     

 :  static int N;  수열 개수
    static int arr[];  수열 배열
    static int cal[] = new int[4];  연산자 배열
    static int max = Integer.MIN_VALUE;  정수 최대값
    static int min = Integer.MAX_VALUE;  정수 최소값

 

 :  N = Integer.parseInt(br.readLine());  첫째줄 입력
    arr = new int[N];  arr배열 크기 지정
   

 :  st = new StringTokenizer(br.readLine());
    for(int i=0;i<N;i++){  두번째 줄 입력 arr배열에 넣기
         arr[i] = Integer.parseInt(st.nextToken());        
    }

 :  st = new StringTokenizer(br.readLine());
    for(int j=0;j<4;j++){ 세번째 줄 입력 cal배열에 넣기
         cal[j] = Integer.parseInt(st.nextToken());
    }

 

 :  Back(arr[0],1);  백트래킹 실행
   

 :  System.out.println(max);  출력1
    System.out.println(min);  출력2
   
    
 :  public static void Back(int step, int index){  백트래킹 실행

 

        if(index == N){  연산횟수가 N만큼 돌아가면 끝
            max = Math.max(max,step);  마지막 N번째 연산 결과인 step과 max 값 비교 후 갱신
            min = Math.min(min,step);   마지막 N번째 연산 결과인 step과 min 값 비교 후 갱신
            return;
        }

        for(int i=0; i<4; i++){  연산자 4종류라서 각 수열마다 모두 돌려보기
            if(cal[i]>0){  연산 배열에 값이 있을 경우 해당 연산자를 통해 아래 함수들 수행

                cal[i]--;  해당 연산자 하나 사용했다는 표시
            
                switch(i){  해당 연산자가 무엇인지 파악
                    case 0:  연산자 + 일 경우
                        Back(step + arr[index], index+1);  연산한 값으로 다시 재귀, index++
                        break;
                 
                    case 1:  연산자 - 일 경우
                        Back(step - arr[index], index+1);  연산한 값으로 다시 재귀, index++
                        break;
                        
                    case 2:   연산자 × 일 경우
                        Back(step * arr[index], index+1);  연산한 값으로 다시 재귀, index++
                        break;
                    
                    case 3:  연산자 ÷ 일 경우
                        Back(step / arr[index], index+1);  연산한 값으로 다시 재귀, index++
                        break;
                }

                cal[i]++;  백트래킹 과정 모두 끝났을 경우 다른 경우의 수 계산을 위해 연산 배열 ++
            }
        }    
    }

 

 

[시간 복잡도]

 

현문제 시간제한 2초이다

 

1억번의 연산 = 1초라 2억번의 연산 안에 완료해야 한다

 

시간 복잡도	최대 N	연산 횟수 한계
O(N)	1억	1억번
O(NlogN)	5백만
O(N^2)	1만
O(N!)	11

 

수열의 최대 개수는 11 / 연산자 최대 개수는 10

연산자는 한번 쓰일 때 4가지의 경우를 갖는다

즉 4 × 4 × 4 × 4 × 4 × 4 × 4 × 4 × 4 × 4 = 4^10 이므로 2억번 보다 적어 수행 가능하다

시간복잡도는 O(4ⁿ) 이다

이제 풀어보러 갈께요 :)

 

 

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

14888번: 연산자 끼워넣기

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *