[SW4008] 숫자 만들기

 SW Expert Academy - 숫자 만들기 

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH&categoryId=AWIeRZV6kBUDFAVH&categoryType=CODE&problemTitle=sw&orderBy=PASS_RATE&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2&&&&&&&&& 

SW Expert Academy

 

문제 입출력

5
2 1 0 1

#1 24

 

문제 풀이

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


public class Solution {
	static int ans, T, N, max, min;
	static int[] number, opt, optTemp, tgt;
	static boolean[] visit;
	static char[] src = { '+', '-', 'x', '/' };

	static StringBuilder sb = new StringBuilder();


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

		T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			// 초기화
			N = Integer.parseInt(br.readLine());
			opt = new int[4];
			optTemp = new int[4];
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 0; i < 4; i++) opt[i] = Integer.parseInt(st.nextToken());
			optTemp = opt.clone();

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

			tgt = new int[N - 1];
			visit = new boolean[4];
			max = Integer.MIN_VALUE;
			min = Integer.MAX_VALUE;
			ans = 0;

			// 탐색
			perm(0);
			ans = Math.abs(max - min);

			// 출력
			sb.append("#").append(t).append(" ").append(ans).append("\n");
		}

		System.out.println(sb.toString());

	} // end main


	private static void perm(int dep) {
		if (dep == N - 1) {
			opt = optTemp.clone();
			if (check()) {
				int sum = calc();
				max = Math.max(max, sum);
				min = Math.min(min, sum);
			}

			return;
		}

		for (int i = 0; i < 4; i++) {
			if (visit[i]) continue;
			tgt[dep] = i;
			perm(dep + 1);
		}
	} // end perm


	// 주어진 연산자를 이용해서 계산하는 함수
	private static int calc() {
		int sum = number[0];

		for (int i = 0; i < N - 1; i++) {
			switch (src[tgt[i]]) {
			case '+':
				sum += number[i + 1];
				break;
			case '-':
				sum -= number[i + 1];
				break;
			case 'x':
				sum *= number[i + 1];
				break;
			case '/':
				sum /= number[i + 1];
				break;
			default:
				break;
			}
		}

		return sum;
	} // end calc


	// 각 연산자의 갯수가 맞는지 확인하는 함수
	private static boolean check() {
		for (int i = 0; i < N - 1; i++) opt[tgt[i]]--;

		for (int i = 0; i < 4; i++) if (opt[i] != 0) return false;

		return true;
	} // end check

}

• 순열을 사용하면 풀리는 문제이다.
• 순열을 이용하여 숫자 사이에 연산자를 자리를 배치한 다음에
• 그렇게 배치된 연산자들이 해당 연산자 개수에 맞는지 check() 를 한다.
• 만약 true 로 떨어진다면 max, min 값을 구한다.
• 그렇게 구한 값을 사용하여 차이를 구해 해결한다.

 

 

 

 

 

 

 

 

 

# SWEA 숫자 만들기 자바 # SW 숫자 만들기 java

---