[ 수학 ] - 연산자 끼워넣기 ( 순열)

백준 14888번을 풀어보다가 도저히 감이안와서 자바 경우의수 알고리즘 이라고 검색하니 

 

맨위에 순열과 조합에관해서 나왔다.

 

일단 둘다 몇개중 몇개를 뽑는 경우의수를 찾는 방식이였다.

 

이때 순열은 숫자의 순서에 영향을 받고 , 조합은 순서에 영향을 받지않앗다

 

예를들어 {1,2,3,4} 중 2개를 뽑는 순열과 , 조합이있다고하면

 

순열은 {1,2} ,{2,1} ....  이 가능하지만 조합은 {1,2} , {2,1} ....  이 불가능하다.

 

이 문제에서는 순열중 nPn 방식을 사용하였는데 nPn 을 구하는 코드를 통해 발생할수있는 연산자의 경우의 수에다가 각 숫자를 대입하여 연산하도록한 후 해당값이 이전 최대값과 , 최소값보다 크거나 작은지 를 체크하여 문제를 해결하였다.

(nPn = 입력과 출력의 갯수가 같음 , nPr = 입력중 r개만 출력 )

 

 

아쉬운점은 n이 5일경우 발생할수 있는 경우의수는 120가지인데 , 이문제에서는 n이 겹칠수가있어 경우의수가 줄어든다.

 

그부분을 제외시키지않고 그냥 120번 다 검사하였다.

 

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

14888번: 연산자 끼워넣기

 

 

import java.util.*;

public class Main {

   static int maxTotal=-1000000000;   // 초기 셋팅값 -10억
   static int minTotal=1000000000;    //초기 셋팅값 10억
   static int[] arr1 =null;
public static void main(String[] args) { 


 Scanner sc = new Scanner(System.in);
 int a = Integer.parseInt(sc.nextLine());    // 입력받을 숫자 수 
 String b = sc.nextLine();   //입력받을 숫자 
 arr1=new int[a];  //입력받은 숫자를 담을 배열
 for(int i=0;i<a;i++) {  //각 숫자를 배열에 나눠담는다
 arr1[i]=Integer.parseInt(b.split(" ")[i]);
 }
 
 String c= sc.nextLine();  //입력받은 연산자 숫자
 String[] arr = new String[a-1];  //입력받을 연산자를 담을 배열
 int tmpCount=0;  //입력받을 연산자 배열위치 
 
 for(int i = 0; i< 4;i++) {  //입력받은 연산자 숫자를 연산자로 치환하여 배열에 담음 
 int j = Integer.parseInt(c.split(" ")[i]);
 for(int k =0 ;  k < j ;k++) {
 if(i==0) {
 arr[tmpCount]="+";
 }else if(i==1) {
 arr[tmpCount]="-";
 }else if(i==2) {
 arr[tmpCount]="*";
 }else if(i==3) {
 arr[tmpCount]="/";
 }
 
 tmpCount++;
 }
 }

      
      //nPn 순열 사용
      doEx(arr,0);
      
      
      System.out.println(maxTotal);  //최대값 
      System.out.println(minTotal);  //최소값 
      
   

}

//nPn 수열구하기 
static void doEx(String[] arr,int idx) {
      int length = arr.length;
      
      if(idx==length-1) {
         int total = 0 ;
         for (int i = 0 ; i <arr.length;i++) {
         //연산자를 숫자 사이에 끼어넣고 차례대로 계산하는 과정 
         // 연산자 배열 0 은 숫자 0 뒤에와야함으로 0일때는 강제로 처리함 
            if(i==0) {
               if(arr[i].contentEquals("+")) {
                  total=arr1[0]+arr1[1];
               }else if(arr[i].contentEquals("-")) {
                  total=arr1[0]-arr1[1];
               }else if(arr[i].contentEquals("*")) {
                  total=arr1[0]*arr1[1];
               }else if(arr[i].contentEquals("/")) {
                  total=arr1[0]/arr1[1];
               }
            }else { // 연산자 배열 1부터는 앞에 계산한 숫자에 처리하면됨 
               if(arr[i].contentEquals("+")) {
                  total+=arr1[i+1];
               }else if(arr[i].contentEquals("-")) {
                  total-=arr1[i+1];
               }else if(arr[i].contentEquals("*")) {
                  total*=arr1[i+1];
               }else if(arr[i].contentEquals("/")) {
                  if(total<0) { // 나눗셈일떄 예외처리 
                     total = total *-1;
                     total/=arr1[i+1];
                     total = total *-1;
                  }else {
                     total/=arr1[i+1];
                  }
                  
               }
            }
            
         }
         
         if(total>maxTotal) maxTotal=total;
         
         if(total<minTotal) minTotal=total;
         return;
      }
      
      
      for(int i=idx;i<length;i++) {
         swap(arr,idx,i);
         doEx(arr,idx+1);
         swap(arr,idx,i);
      }
      
   }
   
   
 static   void swap(String[] arr,int t1, int t2){
      String tmp = arr[t1];
      arr[t1]=arr[t2];
      arr[t2]=tmp;
   }

}

 

 

 

문제 푸는데 하루정도 걸렸던거같다. 순열을 모르고 풀라고했으니...

 

nPn 코드를 익히고 nPr도 같이 익혀야겠다.