백준(BOJ) 2798: 블랙잭

 

출처: https://www.acmicpc.net/problem/2798

3중반복문으로 풀수도 있다. 하지만 나는 사고의 확장성을 위해서 재귀를 택했다. 아래에 반복문을 이용한 코드도 첨부한다. 

어차피 구하고자 하는것은 주워진 숫자들의 목록에서 3개를 택하여 합한 값이므로 1,2,3 을 택하던지 3,2,1을 택하던지 아무 상관없다. 만약 3개의 숫자의 합이아닌 숫자의 목록에서 3개의 수를 문자열로 합한다던가하는 순서에 영향을 받는 값을 구하는 결과라면 일의 자리에 몇번인덱스의 값을 택할지, 십의 자리에 몇번 인덱스의 값을 구할지가 중요해지게 되겠지만 이 문제는 아니다. 따라서 2번째 풀이와 같이 재귀안에서 simple하게 반복문을 구성하는 것이 더 효율적이다. 

첫번째, 나의 풀이. 코드만 봐도 명확한 접근법은 아니라는 것을 알수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Testing3 {
    static class Element {
        public Element(boolean exist, int value) {
            this.exist = exist;
            this.value = value;
        }

        boolean exist;
        int value;
    }

    public static int solution(int target, int cur, int size, Element[] elements) {
        if (size != 3 && target <= cur)
            return 0;
        if (size == 3) {
            if (cur > target) return 0;
            else return cur;
        }
        int candi = cur;
        for (int i = 0; i < elements.length; ++i) {
            if (elements[i].exist) {
                elements[i].exist = false;
                int result = solution(target, cur + elements[i].value, size + 1, elements);
                if (result <= target && result > candi) {
                    candi = result;
                }
                elements[i].exist = true;
            }
        }
        return candi;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Element[] elements = new Element[n];
        for (int i = 0; i < n; ++i)
            elements[i] = new Element(true, arr[i]);
        System.out.println(solution(m, 0, 0, elements));
    }
}

두번째, 다른 블로그 참고한 풀이 ( https://kong-ambition09.tistory.com/58  )

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

public class Testing3 {
    public static int target;
    public static int[] arr;

    public static int solution(int count, int[] numbers, int start) {
        int answer = 0;
        if (count == 3) {
            int temp = 0;
            for (int i = 0; i < 3; ++i) temp += numbers[i];
            if (temp <= target) {
                answer = Math.max(answer, temp);
            }
            return answer;
        }
        for (int i = start; i < arr.length; ++i) {
            numbers[count] = arr[i];
            int result = solution(count + 1, numbers, i + 1);
            if (result > answer) answer = result;
        }
        return answer;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        target = Integer.parseInt(st.nextToken());
        arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] elements = new int[3];
        System.out.println(solution(0, elements, 0));

    }
}

세번째, 3중 반복문 풀이. 직관적이라서 어렵지 않다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int[]arr=new int[n];
        for(int i=0;i<n;i++)
            arr[i]=sc.nextInt();

        int sum=0;
        int answer=0;
        for(int i=0;i<n-2;i++) {
            for(int j=i+1;j<n-1;j++) {
                for(int k=j+1;k<n;k++) {
                    sum=arr[i]+arr[j]+arr[k];
                    if(sum<=m&&answer<sum)
                        answer=sum;
                }
            }
        }
        System.out.println(answer);

    }
}