[SWEA] #4008 - 숫자 만들기

※ 문제에 대한 저작권은 SW Expert Academy에 있습니다.

💡 출처

---

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH 

SW Expert Academy

 

💡 문제

---

[설명]

선표는 게임을 통해 사칙 연산을 공부하고 있다.

N개의 숫자가 적혀 있는 게임 판이 있고, +, -, x, / 의 연산자 카드를 숫자 사이에 끼워 넣어 다양한 결과 값을 구해보기로 했다.

수식을 계산할 때 연산자의 우선순위는 고려하지 않고 왼쪽에서 오른쪽으로 차례대로 계산한다.

예를 들어 1, 2, 3 이 적힌 게임 판에 +와 x를 넣어 1 + 2 * 3을 만들면 1 + 2를 먼저 계산하고 그 뒤에 * 를 계산한다.

즉 1+2*3의 결과는 9이다.

주어진 연산자 카드를 사용하여 수식을 계산했을 때 그 결과가 최대가 되는 수식과 최소가 되는 수식을 찾고, 두 값의 차이를 출력하시오.

 

[예시]

[Figure 1]과 같이 [3,5,3,7,9]가 적힌 숫자판과 [‘+’ 2개, ‘-‘ 1개, ‘/’ 1개]의 연산자 카드가 주어진 경우를 생각해보자.

[Figure 1]

아래 [Table 1]은 만들 수 있는 수식과 계산 결과이다.

수식	수식의 계산 결과
3 + 5 + 3 - 7 / 9	0
3 + 5 + 3 / 7 - 9	-8
3 + 5 - 3 + 7 / 9	1
3 + 5 - 3 / 7 + 9	9
3 + 5 / 3 + 7 - 9	0
3 + 5 / 3 - 7 + 9	4
3 / 5 + 3 + 7 - 9	1
3 / 5 + 3 - 7 + 9	5
3 / 5 - 3 + 7 + 9	13
3 - 5 + 3 + 7 / 9	0
3 - 5 + 3 / 7 + 9	9
3 - 5 / 3 + 7 + 9	16

[Table 1]

이 경우 최댓값은 3 - 5 / 3 + 7 + 9 = 16, 최솟값은 3 + 5 + 3 / 7 - 9 = -8이다.

즉 결과는 최댓값과 최솟값의 차이 ( 16 - ( -8 ) )로 24 가 답이 된다.

 

💡 아이디어

---

연산자의 순서를 고려해서 DFS를 이용한 완전 탐색으로 문제를 해결할 수 있다.

우선 연산자와 피연산자를 서로 다른 배열로 관리한다.

그리고 DFS를 이용해 연산자의 모든 순서를 고려해본다.

예를 들어  연산자가 '+'라면 피연산자 2개를 더한 결과를 가지고 DFS를 재귀 호출한다.

그리고 그 뒤에 나오는 연산자가 '*'라면 피연산자 2개를 곱한 결과를 가지고 DFS를 재귀 호출한다.

이 과정을 반복하다가 피연산자를 모두 사용하면 기존의 최댓값, 최솟값과 비교해 갱신한다.

 

💡 소스코드

---

package SWEA;

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

public class SWEA_P4008_숫자_만들기 {
	static int N;
	static int[] op;
	static int[] num;
	static int max;
	static int min;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("./SWEA_INPUT/SWEA_P4008_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer sz;
		int T = Integer.parseInt(br.readLine());

		for (int TC = 1; TC <= T; TC++) {
			N = Integer.parseInt(br.readLine());
			op = new int[4];
			num = new int[N];

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

			sz = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++)
				num[i] = Integer.parseInt(sz.nextToken());

			max = Integer.MIN_VALUE;
			min = Integer.MAX_VALUE;

			DFS(1, num[0]);
			System.out.println("#" + TC + " " + (max - min));
		}
		br.close();
	}

	public static void DFS(int idx, int result) {
		if (idx >= N) {
			max = max > result ? max : result;
			min = min < result ? min : result;
			return;
		}

		for (int i = 0; i < 4; i++) {
			if (op[i] > 0) {
				op[i]--;

				if (i == 0)
					DFS(idx + 1, result + num[idx]);

				else if (i == 1)
					DFS(idx + 1, result - num[idx]);

				else if (i == 2)
					DFS(idx + 1, result * num[idx]);

				else if (i == 3)
					DFS(idx + 1, result / num[idx]);

				op[i]++;
			}
		}
	}
}

 

💡 결과

---