[모의 SW 역량테스트] 숫자 만들기 -Java

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH&categoryId=AWIeRZV6kBUDFAVH&categoryType=CODE

SW Expert Academy

package SW_Expert_Academy;

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

public class 숫자만들기 {
	static int N, max, min, nums[], op[];

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			max = Integer.MIN_VALUE;
			min = Integer.MAX_VALUE;
			op = new int[4];
			nums = new int[N];

			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 0; i < 4; i++) {
				op[i]=Integer.parseInt(st.nextToken());
			}

			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				nums[i] = Integer.parseInt(st.nextToken());
			}
			
			solve(0,op[0],op[1],op[2],op[3], nums[0]);
			System.out.println("#"+tc+" "+(max-min));
		}

	}

	private static void solve(int cnt, int plus, int minus, int mul, int div, int result) {
		if(cnt==N-1) {
			max=Math.max(result, max);
			min=Math.min(result, min);
			return;
		}
		if(plus>0) solve(cnt+1, plus-1, minus, mul, div, result+nums[cnt+1]);
		if(minus>0) solve(cnt+1, plus, minus-1, mul, div, result-nums[cnt+1]);
		if(mul>0) solve(cnt+1, plus, minus, mul-1, div, result*nums[cnt+1]);
		if(div>0) solve(cnt+1, plus, minus, mul, div-1, result/nums[cnt+1]);
	}
}

소요시간 : 35분

 

처음에 연산자를 조합을 이용해 만들고 계산을 하려고 했습니다.

하지만 연산자의 개수가 최대 11인 것을 보고 조합으로는 안 되겠다 싶어서 다른 방법을 찾아봤습니다.

 

문제를 보니 무조건 완전탐색 문제였고 dfs가 떠올라서 dfs 방식대로 풀었습니다!

 

우선 op라는 배열에 0인덱스부터 차례대로 + - * / 연산자가 몇 개씩 들어있는지 저장해줍니다.

 

그리고 dfs의 인자로 연산자의 갯수를 줍니다.

 

연산을 할 때 마다 각 연산자의 숫자를 줄여주면서 계산합니다. 

 

그러다 N-1번 만큼 수행을 했다면 최댓값, 최솟값을 계산합니다! 끝