[ java ] 백준 (2798 블랙잭)

백준 2798번 블랙잭

(브론즈 2)

 

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

2798번: 블랙잭

 

 

 

(정답 코드)

import java.util.Scanner;

public class Main {
	
public static void QuikSort(int a[], int left, int right) {
		
		int pl=left;
		int pr=right;
		int x=a[(pl+pr)/2];
		
		do {
			while(a[pl]<x) pl++;
			while(a[pr]>x) pr--;
			if(pl<=pr) {
				//스왑
				int temp=a[pl];
				a[pl]=a[pr];
				a[pr]=temp;
				
				//스왑하고 마저 진행
				pl++;
				pr--;
			}
			
		}while(pl<=pr);
		
		if(left<pr) QuikSort(a, left, pr);
		if(right>pl) QuikSort(a, pl, right);
	}

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		
		int n=s.nextInt();
		int m=s.nextInt();
		int [] a = new int [n];
		
		for(int i=0; i<n; i++) {
			a[i]=s.nextInt();
		}
		
		int [] sum=new int[n*(n-1)*(n-2)]; //가능한 모든 합 담을 배열
		int index=0; //sum배열 인덱스 값
		
		
		//중복하지 않는 서로 다른 인덱스로 세 카드를 뽑는다!
		for(int i=0; i<n; i++) {
			for(int j=0; j<n ; j++) {
				if(j==i) {
					continue;
				}
				for(int k=0; k<n ; k++) {
					if(j==k || i==k) {
						continue;
					}
					
					sum[index]=a[i]+a[j]+a[k];
					index++;
				}
			}
		}
		
		QuikSort(sum, 0, sum.length-1);
		
		int res=0;
		
		for(int i=0; i<index; i++) {
			if(m<sum[i]) {
				break;
			}
			res=sum[i];
		}
		
		
		System.out.println(res);
		
	}

}

 

📖 풀이 요약

간단히 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법인 완전 탐색 문제이다 :)

m이랑 같기 전까진 모든 경우의 수를 탐색해보는 문제이다.

 

그래서 for 반복문으로 겹치지않는 세 가지 인덱스 ijk를 선택하고,

해당 인덱스의 세 카드를 뽑아 합을 만드는 모든 경우를 다 고려해 sum 배열에 넣었다.

그리고 퀵 정렬 메소드를 활용해 오름차순으로 배열을 정렬하고,

m보다 커지면 반복문을 나오도록 설정해 m과 가장 근사한 합의 값을 얻도록 했다.