[백준] code.plus(브루트포스 - 재귀,JAVA)15658번, 연산자 끼워넣기(2)

문제 링크

15658번: 연산자 끼워넣기 (2)

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

이 문제에 핵심은

1. N개의 수를 덧셈, 뺄셈, 곱셈, 나눗셈으로 나올 수 있는 최대값과 최솟값을 출력합니다.

2. 덧셈, 뺄셈, 곱셈, 나눗셈의 개수만큼만 사용할 수 있습니다.

 

덧셈, 뺄셈, 곱셈, 나눗셈에 개수를 고려한 모든 경우의 수의 결과를 구합니다.

 

모든 경우 결과 중 최소값과 최대값을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 수열 및 연산자에 대한 정보를 저장하였습니다.
• 모든 경우에서 최대값 및 최소값을 구하는 cal 함수를 실행하였습니다.
• 최대값과 최소값을 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal함수는 연산자의 수를 고려하여 재귀를 통해 모든 경우를 구하여 최대값과 최소값을 구합니다.

 

import java.io.*;
import java.util.*;

public class Main {
	static int N,min = Integer.MAX_VALUE,max = Integer.MIN_VALUE;
	static int[] num;	//수열의 값을 저장하는 배열
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
    	N = Integer.parseInt(br.readLine());
    	num = new int[N];
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //수열의 값 저장
    	for(int i=0;i<N;i++) 
    		num[i] = Integer.parseInt(st.nextToken());
    	st = new StringTokenizer(br.readLine()," ");
    	//연산자 개수 저장
    	int plus = Integer.parseInt(st.nextToken());
    	int minus = Integer.parseInt(st.nextToken());
    	int mul = Integer.parseInt(st.nextToken());
    	int div = Integer.parseInt(st.nextToken());
    	
    	cal(plus,minus,mul,div,1,num[0]);	//모든 경우의 결과 구하는 함수 실행
    	bw.write(max + "\n" + min);	//최대값과 최소값 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //연산자 개수를 고려하여 모든 경우의 결과를 구하는 함수
    static void cal(int plus,int minus, int mul, int div,int length,int cur) {
    	if(length==N) {		//연산 완성시.
    		min = Math.min(min, cur);	//최대값 비교
    		max = Math.max(max, cur);	//최소값 비교
    		return;
    	}
    	if(plus!=0)	//덧셈 개수 남을 때
    		cal(plus-1,minus,mul,div,length+1, cur+num[length]);
    	if(minus!=0)	//뺄셈 개수 남을 때
    		cal(plus,minus-1,mul,div,length+1,cur-num[length]);
    	if(mul != 0)	//곱셈 개수 남을 때
    		cal(plus,minus,mul-1,div,length+1,cur*num[length]);
    	if(div != 0)	//나눗셈 개수 남을 때
    		cal(plus,minus,mul,div-1,length+1,cur/num[length]);
    }
}