[Unsolved][JAVA] SWEA 4008 숫자 만들기

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

SW Expert Academy

 

1. 서론

 

우습게 봤다가(사실 별로 우습게 보지도 않았음) 큰코다친 문제.

중복순열 같아 보였는데 중복순열로 구현할 자신이 없어서(방법이 생각 안 남) 그냥 순열로 구현했다가 시간 초과 나서 결국엔 인터넷을 참조해서 중복순열로 구현했다.

 

2. 문제 풀이

 

숫자가 적힌 배열이 주어지고 연산자가 적힌 배열이 주어진다.

근데 이때 연산자가 그냥 주어지는 것이 아니라 +, -, /, * 중에 몇 개인지 개수로 주어진다.

이 숫자의 순서는 변하지 않고, 연산자 우선순위도 고려하지 않을 때, 즉 숫자들 사이에 연산자를 끼워넣었을 때의 최댓값과 최솟값의 차를 구하는 문제이다.

 

나는 그래서 처음에는 중복순열을 생각했다. 중복순열이 맞다. 근데 특정 연산자만 중복으로 골라서 순열을 어떻게 만들지 모르겠어서 그냥 직접 중복되는 수만큼 똑같은 연산자를 더 배열에 넣어서 그중 선택하게 하는 순열로 풀었다. 그런데 답이 다 나오긴 했으나 중복되는 계산이 너무 많아서 결국엔 시간 초과로 fail이 뜨고 말았다.

 

그래서 결국에는 '특정 연산자만 중복으로 고르게 하는 방법' 을 찾기 위해 인터넷을 참조했는데 답은 백트래킹이었다. 백트래킹으로 일종의 중복순열을 구현하는 것이다. 

 

ex)

op[0] = 2; //+

op[1] = 1; // -

op[2] = 0; // *

op[3] = 1; // /

 

이런 식으로 연산자가 주어진다고 쳤을 때 어떻게 백트래킹을 구현할 것인가?

op[i]의 값을 모두 0으로 만드는 것이 연산자를 전부 사용하는 경우를 의미하므로 op배열을 돌면서 그 값이 0보다 큰 경우에 ++, -- 하면서 순서를 정해주면 되는 것이다. 생각보다 코드가 간단한데 발상은 절대로 못할 것 같아서 충격...

 

 

3. 코드 설명

 

import java.io.*;
import java.util.*;

public class Solution {
	
	static int n, mx, mn;
	static int[] op, num, order;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		for (int p = 1; p <= T; p++) {
			n = Integer.parseInt(br.readLine());

			op = new int[4]; //+(0),-(1),*(2),/(3)
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 0; i < 4; i++)
				op[i] = Integer.parseInt(st.nextToken());
		
			num = new int[n];
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < n; i++)
				num[i] = Integer.parseInt(st.nextToken());
			
			order = new int[n - 1];
			mn = Integer.MAX_VALUE;
			mx = Integer.MIN_VALUE;
		
			dfs(0);
			sb.append("#" + p + " " + (mx - mn) + "\n");
		}
		bw.write(sb.toString());
		bw.close(); br.close();
	}
	
	public static int calc(int a, int op, int b) { //연산자 처리
		switch(op) {
			case 0:
				return (a + b);
			case 1:
				return (a - b);
			case 2:
				return (a * b);
			case 3:
				return (a / b);
		}
		return -1;
	}
	
	public static void dfs(int cnt) {
		if (cnt == n - 1) {
			int sum = calc(num[0], order[0], num[1]);
			
			for (int i = 1; i < n - 1; i++)
				sum = calc(sum, order[i], num[i + 1]);
			
			mx = Math.max(mx, sum);
			mn = Math.min(mn, sum);
			return;
		}
		
		for (int i = 0; i < 4; i++) { //백트래킹으로 연산자 순서 정함(일종의 중복 순열)
			if (op[i] > 0) {
				op[i]--;
				order[cnt] = i;
				dfs(cnt + 1);
				op[i]++;
			}
		}
	}
}

 

값들을 입력받고 dfs(백트래킹)을 돌려준다. 위의 설명처럼 op[i] 값을 사용했다고 가정하고 order 배열에 그 연산자를 뜻하는 숫자 i를 순서대로 넣어준 후 n-1만큼 연산자 순서를 다 뽑았으면 순서대로 값을 계산해서(이 부분도 누적으로 계산하는 것 때문에 약간 헤맴) 값을 구한다. 그리고 이 값을 최댓값, 최솟값 구하는 함수에 넣고 돌린 후 각자 해당하는 값에 저장한다. 이를 통해 모든 경우를 다 돌고 나면 최댓값과 최솟값의 차를 구했다.

 

아이디어가 너무 생각지도 못했지만 어렵지도 않은 것 같아서 기억에 남겨두기 위해 블로그에 메모...