4008번 - 숫자 만들기

문제의 저작권은 SW Expert Academy에 있습니다.

1. 문제
    1-1. 링크
    1-2. 문제 해석
2. 코드
3. 실행시간

 

 

 

---

 

1. 문제

1-1. 링크

SW Expert Academy

 

1-2. 문제 해석

주어진 연산자와 숫자로 최댓값, 최솟값을 구하는 문제이다.

연산자의 우선 순위를 고려하지 않고 왼쪽부터 차례대로 계산한다는 특징만 유의하면 될 것 같다.

 

가능한 수식을 모두 계산해봐야하기 때문에 완전탐색을 사용했다.

크게 어렵지 않은 문제라 적을 내용이 딱히 없는 것 같다.

 

2. 코드

public class Day15_숫자만들기 {
	static int[] symbol;
	static int[] numbers;
	static final int SYMCNT = 4;
	static int max;
	static int min;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		int testCase = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= testCase; tc++) {
			int N = Integer.parseInt(br.readLine());

			// 연산자
			symbol = new int[SYMCNT];
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < SYMCNT; i++) {
				symbol[i] = Integer.parseInt(st.nextToken());
			}

			// 숫자
			numbers = new int[N];
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				numbers[i] = Integer.parseInt(st.nextToken());
			}

			max = Integer.MIN_VALUE;
			min = Integer.MAX_VALUE;
			dfs(numbers[0], 1, N - 1);
			sb.append("#").append(tc).append(" ").append(max - min).append("\n");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	public static void dfs(int sum, int idx, int left) {
		if (left == 0) {
			if (sum > max) max = sum;
			if (sum < min) min = sum;
			return;
		}

		for (int i = 0; i < SYMCNT; i++) {
			if (symbol[i] > 0) {
				symbol[i]--;
				dfs(calc(sum, numbers[idx], i), idx + 1, left - 1);
				symbol[i]++;
			}
		}
	}

	public static int calc(int n1, int n2, int sym) {
		switch (sym) {
		case 0:
			return n1 + n2;
		case 1:
			return n1 - n2;
		case 2:
			return n1 * n2;
		default:
			return n1 / n2;
		}
	}
}

 

 

3. 실행시간

실행결과

 

완전 탐색이라 되게 느릴 줄 알았는데 생각보다 빨랐다.