[문제] 백준 2798번 블랙잭

* 출처: 백준 단계별로 풀어보기 브루트 포스 편

www.acmicpc.net/problem/2798

2798번: 블랙잭

내 생각

 

1. 첫번째 풀이

1시간 정도 고민하다가 더이상 생각을 못하겠어서 못 풀었다. 

ArrayList를 써보고 싶어서, 블랙잭 카드를 list에 담고, 애초에 정렬했다.

그 후에 스택에다가 list의 인덱스를 push해서 완전 탐색하는 방법을 고민하다가 머리 빠개질 거 같아서 그만 뒀다...

 

그냥 3중 for 문 돌리면 끝이었다.

아래는 다른 분 코드 참고한 것

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int N = Integer.parseInt(st.nextToken()); // 카드 수
		int M = Integer.parseInt(st.nextToken()); // 최대값

		int[] arr = new int[N];

		st = new StringTokenizer(in.readLine(), " ");
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int result = search(arr,N,M);
		System.out.println(result);
	}

	static int search(int[] arr, int N, int M) {
		int result = 0;
		for(int i=0;i<N-2;i++) {
			// 첫번째 카드가 M보다 크면 건너뛰기
			if(arr[i]>M) continue;
			
			for(int j=i+1;j<N-1;j++) {
				
				// 첫번째 + 두번째 카드 합이 M보다 크면 건너뛰기
				if(arr[i]+ arr[j]> M) continue;
				
				for(int k=j+1;k<N;k++) {
					// 세 카드의 합 구해보기
					int tmp = arr[i] + arr[j]+ arr[k];
					//최대값이랑 똑같다면 바로 리턴
					if(tmp == M) return tmp;
					// M 보다는 작지만 그전의 합보다 크면 result 갱신
					if(result<tmp && tmp<M) {
						result = tmp;
					}
				}
			}
		}
		return result;
	}
}

2. 두번째 풀이

 

이 문제는 조합 문제이다! 재귀적으로 다시 풀어봤다.

public class Main {
	static int N;	//카드 수
	static int M;	// 최대값
	static int[] arr;
	static int[] numbers; // 조합
	static int sum = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		N = Integer.parseInt(st.nextToken()); // 카드 수
		M = Integer.parseInt(st.nextToken()); // 최대값

		arr = new int[N];
		numbers = new int[3];
		st = new StringTokenizer(in.readLine(), " ");
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		search(0,0);
		System.out.println(sum);
	}
	
	static void search(int cnt, int start) {
		if(cnt == 3){
			int tmp = 0;
			for(int i=0;i<3;i++) {
				tmp += numbers[i];
			}
			if(tmp<=M)
				sum = Math.max(tmp, sum);
			return;
		}
		
		for(int i=start;i<N;i++) {
			numbers[cnt] = arr[i];
			search(cnt+1, i+1);
		}
	}
}