백준 2798번 블랙잭

 

문제 링크 : https://www.acmicpc.net/problem/2798

2798번: 블랙잭

 

기본적인 완전탐색 문제다.

알고리즘이 너무 오랜만이라 다 까먹어서 처음부터 다시 공부하는 느낌으로 풀었다.

다 풀고나서 다른 사람의 풀이를 보니 재귀함수를 다르게 구현하면 코드가 훨씬 간단해진다는 것을 알고 씁쓸해졌다..

 

소스코드

 

import java.util.ArrayList;
import java.util.Scanner;
 
public class Main {
    
    static int m, answer=0;
    static int[] card;
    static ArrayList<Integer> indexAr = new ArrayList<Integer>();
    
    static public void recur(int n, int toPick) {
        if(toPick==0) {
            compare();
            return;
        }
        int smallest = indexAr.isEmpty() ? 0 : indexAr.get(indexAr.size()-1) + 1;
        
        for(int i= smallest; i<n; i++) {
            indexAr.add(i);
            recur(n, toPick-1);
            indexAr.remove(indexAr.size()-1);
        }
    }
    
    public static void compare() {
        int tot=0, al = indexAr.size();
    
        for(int i=0; i<al; i++) {
            tot += card[indexAr.get(i)];
        }
        if (tot > m) return;
 
        answer = Math.max(answer, tot);
    }
 
    public static void main(String[] args) {
        int n;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        card = new int[n];
        
        for(int i=0; i<n; i++) {
            card[i] = sc.nextInt();
        }
        
        recur(n, 3);
        System.out.println(answer);
    }
}