14888번) 연산자 끼워넣기

문제 출처 : https://www.acmicpc.net/problem/14888

DFS죠??

2018년 4월 6일 - 다듬지 않은 시험용 코드 (소요시간 : 29분)  public class Q14888 { static int max = 0, min = 0; static int maxCount; static int[] operator, values; static boolean isFirst = true; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int size = sc.nextInt(); values = new int[size]; for (int i = 0; i < size; i++) { values[i] = sc.nextInt(); } maxCount = 0; operator = new int[4]; for (int i = 0; i < 4; i++) { int temp = sc.nextInt(); operator[i] = temp; maxCount += temp; } for (int i = 0; i < 4; i++) { if (operator[i] > 0) { operator[i] -= 1; calResult(1, i, values[0]); operator[i] += 1; } } System.out.println(max + "\n" + min); } static void calResult(int count, int what, int result) { switch (what) { case 0: result += values[count]; break; case 1: result -= values[count]; break; case 2: result *= values[count]; break; case 3: if (result >= 0) { result /= values[count]; } else { result *= -1; result /= values[count]; result *= -1; } break; } if (count == maxCount) { if (!isFirst) { if (result > max) { max = result; } if (result < min) { min = result; } } else { isFirst = false; max = result; min = result; } return; } for (int i = 0; i < 4; i++) { if (operator[i] > 0) { operator[i] -= 1; calResult(count+1, i, result); operator[i] += 1; } } } }

2018년 4월 12일 - 다듬지 않은 코드 (소요시간 : 27분) import java.util.Scanner; public class Q14888 { static long[] values; static int[] operator = new int[4]; static int size; static long min = -1, max = -1; static boolean isFirst = true; public static void main(String[] args) { Scanner sc = new Scanner(System.in); size = sc.nextInt(); values = new long[size]; for (int i = 0; i < size; i++) { values[i] = sc.nextInt(); } for (int i = 0 ; i < 4; i++) { operator[i] = sc.nextInt(); } doCal(values[0], 1); System.out.println(max + "\n" + min); } static void doCal(long result, int count) { // System.out.println(result); if (count == size) { // System.out.println(tempResult); if (isFirst) { isFirst = false; min = result; max = result; return; } if (min > result) { min = result; } if ( max < result) { max = result; } return; } for (int i = 0; i < 4; i++) { if (operator[i] > 0) { operator[i] -= 1; long tempResult = getCalResult(result, i, values[count]); doCal (tempResult, count+1); operator[i] += 1; } } } static long getCalResult(long nowNum, int what, long nextNum) { switch (what) { //+ case 0 : nowNum += nextNum; break; //- case 1 : nowNum -= nextNum; break; //* case 2 : nowNum *= nextNum; break; //나누기 case 3 : if (nowNum > 0) { nowNum /= nextNum; } else { nowNum *= -1; nowNum /= nextNum; nowNum *= -1; } break; } return nowNum; } }