백준 14888번

재귀로 풀었다.

어차피 n의 최대 수는  11이고 연산자의 최대는 10, 즉 2 3 2 3 으로 나오고 처음으로 나오는 0이 가장 적을 때니까

 

2323 = 4

2223 = 4

2222 = 4

1222 = 4

1122 = 4

1112 = 4

1111 = 4

0111 = 3

0011 = 2

0001 = 1

0000 = 1

으로

나오는 경우의 수는 98304인 것 같다.

단순하게 4의 11승으로 계산해도 백만 대에서 멈추기 때문에 상관없다.

그냥 재귀 돌려도 된다. 아이디어는 다음과 같다.

 

 

 

1. 재귀를 이용해서 푼다.

(base case는 depth가 nums 배열의 length -1과 같을 때, or 수식 배열의 모든 원소가 0일때), 즉 모든 원소에 대한 식을 끝마쳤을 때

 

2. 수식의 개수를 배열에 넣는다고 가정했을 때, 수식 배열의 length는 무조건 4이고 그 안에는 정수가 들어있다.

 

3. 그렇게 된다면 recursive case를 4개 만들어 주고 base case로 배열에 0보다 작은 수가 들어가게 된다면 바로 리턴을 해준다.

(recursive case에 plus >0 라는 if문을 바로 위에 걸어주면 시간복잡도적 측면에서 더 좋을 것 같은데 어차피 시간도 널널해서 재귀 한번 더돌고 위쪽에서 return하게 걸었다.)

 

(솔직히 배열 만들 필요도 없고 그냥 int로 선언해도 될 것 같은데 그냥 만들어봤다.)

이런 문제만 있으면 좋겠다.

 

package programers;

import java.util.Arrays;
import java.util.Scanner;

public class BOJ14888 {
    static int[] nums;
    static int[] count = new int[4];
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        for (int i = 0; i < 4; i++) {
            count[i] = sc.nextInt();
        }
        recur(nums[0], 0, count[0], count[1], count[2], count[3]); // sum의 첫 값에는 첫번째 index값
        System.out.println(max);
        System.out.println(min);
    }


    public static void recur(int sum, int depth, int plus, int minus, int mul, int div) {
        if (plus < 0 || minus < 0 || mul < 0 || div < 0) {
            return; // 카운트 없는거 썼으면 바로 return해서 다음 recursive case로 돌아간다.
        }
        if (depth == nums.length - 1) {
            max = Math.max(max, sum); // 상황에 맞게 돌았으면 max, min 업데이트 해준다.
            min = Math.min(min, sum);
            return;
        }

        recur(sum + nums[depth + 1], depth + 1, plus - 1, minus, mul, div);
        recur(sum - nums[depth + 1], depth + 1, plus, minus - 1, mul, div);
        recur(sum * nums[depth + 1], depth + 1, plus, minus, mul - 1, div);
        recur(sum / nums[depth + 1], depth + 1, plus, minus, mul, div - 1);

    }
}