[백준] 14888 연산자 끼워넣기, java

14888번: 연산자 끼워넣기

문제 간단 설명

 

주어진 수와 주어진 연산자의 개수를 가지고 구할 수 있는 최댓값, 최솟값을 구하는 문제입니다. 주어진 수의 배치는 변경할 수 없으며, 연산은 무조건 왼쪽부터 시행한다는 조건이 가지고 있어 그렇게 어려워 보이지는 않는 문제였습니다.

---

문제 풀이

 

저는 dfs를 이용하여 풀어보았습니다. 생각을 떠오르기 전에는 뭔가 힘들었는데 dfs로 풀면 되겠다라고 떠오르고 나니 생각보다 쉽게 해결을 한 문제입니다. 사실 숫자와 연산자를 따로 index를 주어야 하는 것에서 조금 어려웠습니다.

---

코드 

package com.baekjoon.silver;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main_BJ_14888_S1_연산자끼워넣기 {
	static int N;
	static int max, min;
	static int[] nums;
	static boolean[] visited;
	static boolean first;
	static ArrayList<Integer> cmd;
	
	//dfs를 이용한 풀이를 만들어 보았습니다.
	public static void dfs(int cnt, int now) {
		
		//만약 연산자를 모두 사용했다면 현재 연산의 값으로 max, min값을 갱신해줍니다.
		if(cnt == N) {
			//처음으로 나온 값은 무조건 max, min에 넣어줍니다.
			if(!first) {
				max = now;
				min = now;
				first = true;
			}
			
			max = Math.max(max,  now);
			min = Math.min(min,  now);
			return;
		}
		
		//연산자의 수만큼 돌며 dfs를 실행합니다.
		for (int i = 0; i < cmd.size(); i++) {
			if(visited[i]) continue;
			visited[i] = true;
			
			//각각의 숫자에 맞는 연산을 진행시켜 줍니다.
			if(cmd.get(i) == 0) {
				dfs(cnt+1, now+nums[cnt]);
			} else if(cmd.get(i) == 1) {
				dfs(cnt+1, now-nums[cnt]);
			} else if(cmd.get(i) == 2) {
				dfs(cnt+1, now*nums[cnt]);
			} else {
				dfs(cnt+1, now/nums[cnt]);
			}
			visited[i] = false;
		}
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		nums = new int[N];
		cmd = new ArrayList<>();
		first = false;	//처음 발견하는 값을 max, min 모두에 넣어주어 시작 숫자를 만들어주기 위함 입니다.
		
		//데이터 입력
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
		visited = new boolean[N-1];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < 4; i++) {
			int k = Integer.parseInt(st.nextToken());
			for (int j = 0; j < k ; j++) {
				cmd.add(i);
			}
		}
		
		//첫번째 숫자는 항상 같으므로 넣어주고 시작을합니다.
		dfs(1, nums[0]);
		
		System.out.println(max);
		System.out.println(min);
	}
}