[IM 대비] BOJ_2798 블랙잭

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

2798번: 블랙잭

 

 

처음엔 부분집합을 사용했는데 시간초과가 났다.. 심지어 subset 함수 구현은 생각이 잘 안나서 youtube live 코드를 참고했는데도 틀려서 화가 났다! 다른 사람들은 대체 어떻게 푼거지 싶어서 구글을 살짝 봤다. 자세히는 안보고 전체 구조만 휘리릭 봤는데 for문을 몇개씩 쓰는 것 같은데도 잘 돌아간다고 해서 나도 전략을 바꿔서 두번째 방법으로는 카드 3장을 뽑는다는 아이디어에 착안하여 for문 3개를 사용했다.

 

package IM1;

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

public class BOJ_2798 {
	
	public static boolean[] isSelected;
	public static int N, M;
	public static int max = Integer.MIN_VALUE;
	public static int[] cards;
	public static int[] result;
	
	public static void subset(int cnt) {
		
		if (cnt==N) {
			int sum = 0;
			for (int i = 0; i < isSelected.length; i++) {
				if (isSelected[i]) {
					sum = sum + cards[i];
				}
				if (sum<=M && sum>max) {
					max = sum;
				}
			}
			return;
		}
		
		isSelected[cnt] = false;
		subset(cnt+1);
		isSelected[cnt] = true;
		subset(cnt+1);
	}
	
	public static void main(String[] args) {
		
		StringBuilder sb = new StringBuilder();
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		sc.nextLine();
		
		cards = new int[N];
		isSelected = new boolean[N];
		for (int i = 0; i < cards.length; i++) {
			cards[i] = sc.nextInt();
		}
		//System.out.println(Arrays.toString(cards));
		subset(0);
		System.out.println(max);
	}
}

 

package IM1;

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

public class BOJ_2798_re {
	
	public static void main(String[] args) {
		
		StringBuilder sb = new StringBuilder();
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		sc.nextLine();
		
		int[] cards = new int[N];
		for (int i = 0; i < cards.length; i++) {
			cards[i] = sc.nextInt();
		}
		//System.out.println(Arrays.toString(cards));
		
		int max = Integer.MIN_VALUE;
		int sum = 0;
		
		for (int a = 0; a < N; a++) {
			for (int b = a+1; b < N; b++) {
				for (int c = b+1; c < N; c++) {
					sum = cards[a] + cards[b] + cards[c];
					//System.out.print(cards[a] + " + " + cards[b] + " + " + cards[c]);
					//System.out.println(" = " + sum);
					if (sum>max && sum<=M) {
						max = sum;
						//System.out.println(max);
					}
				}
			}
		}
		System.out.println(max);
	}
}