[백준] 15658 연산자 끼워넣기 (2)

1. 문제

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

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

2. 접근방법

각 자리에 연산자를 집어넣었을 때 최소값과 최댓값을 찾는 문제

 

사칙연산 순서에 상관없이 앞에서부터 계산하기 때문에 dfs로 해결하기 좋은 문제라 생각했다.

 

배열 하나에 연산자의 갯수를 넣어두고

 

연산자가 남아있으면 꺼내쓰면서 갯수를 줄이고

연산자가 없다면 다음 연산자를 꺼내 쓰고

 

모든 연산이 끝나면 돌아와서

갯수 줄였던 연산자 다시 집어 넣고

그 다음 연산자를 꺼내쓰고

 

이런식으로 dfs로 트리 탐색하듯이 풀면 간단히 해결이 가능하다.

3. 자바 코드

package Silver;

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

public class P15658연산자끼워넣기 {
	static int N, min, max;
	static int nums[];
	static int operator[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		min = Integer.MAX_VALUE;
		max = Integer.MIN_VALUE;
		nums = new int[N];
		operator = new int[4];
		for (int i = 0; i < N; i++)
			nums[i] = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < 4; i++)
			operator[i] = Integer.parseInt(st.nextToken());
		dfs(nums[0],1);
		System.out.println(max);
		System.out.println(min);
	}

	public static void dfs(int result, int idx) {
		if (idx == N) {
			max = Math.max(result, max);
			min = Math.min(result, min);
			return;
		}
		for (int i = 0; i < 4; i++) {
			int num = 0;
			if (operator[i] == 0)
				continue;
			operator[i]--;
			if (i == 0)
				num = result + nums[idx];
			else if (i == 1)
				num = result - nums[idx];
			else if (i == 2)
				num = result * nums[idx];
			else if (i == 3)
				num = result / nums[idx];
			dfs(num,idx+1);
			operator[i]++;

		}
	}

}

4. 마치며

재귀 조아