[Java] 백준알고리즘 #2798 블랙잭

백준알고리즘 #2798 블랙잭 문제

주어진 수들을 조합하여 3장의 카드를 골라 합이 m에 가장 근접하게 하는 문제이다.

 

이 문제는 선택정렬을 이용하여 풀면 간단하게 해결할 수 있다.

선택정렬

흔히 최소값, 최대값 또는 오름차순정렬 등을 할 때 많이 사용되는 선택정렬은

1회전에서 1번 원소를 2번 원소부터 시작해 3,4 ... n번째 원소까지 비교하고

2회전에서 2번 원소를 3번 원소부터 시작해 4,5 ... n번째 원소까지 비교하는 방식이다.

이 선택정렬을 이용한다면 1~5까지의 수 중 2개를 뽑아내어 만들 수 있는 순서쌍을 구할 수 있다.

 

예시를 보자

int[] a = { 1, 2, 3, 4, 5 };
for (int i = 0; i < a.length; i++) {
	for (int j = i + 1; j < a.length; j++) {
		System.out.println(a[i] + " " + a[j]);
	}
}

예시 결과

위처럼 선택 정렬을 이용하면 순서쌍을 쉽게 구할 수 있다.

 

이 뿐 아니라 2개의 순서쌍을 구할 땐 2중 for문을 사용했지만

3중 for문을 이용하여 3개의 순서쌍도 구할 수 있는데 이는 다음과 같이 구하면 된다.

int[] a = { 1, 2, 3, 4, 5 };
for (int i = 0; i < a.length; i++) {
    for (int j = i + 1; j < a.length; j++) {
        for (int k = j + 1; k < a.length; k++) {
			System.out.println(a[i] + " " + a[j] + " " + a[k]);
		}
	}
}

예시 결과 2

 

 

위 문제는 주어진 수 중 3개를 뽑아내야 하므로 3중 for문을 사용하면 된다.

그리고 3개의 수의 합이 m에 가장 근접해야 하므로 if문을 사용하여 조건을 달아주면 되겠다.

 

 

전체 코드를 보면 다음과 같다.

import java.util.Scanner;

public class Back2798 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n, m;
		n = sc.nextInt();
		m = sc.nextInt();
		int[] a = new int[n];
		int sum = 0;
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				for (int k = j + 1; k < n; k++) {
					if(sum < a[i] + a[j] + a[k]) {
						if(a[i] + a[j] + a[k] <= m)
							sum = a[i] + a[j] + a[k];
					}
						

				}
			}
		}
		System.out.println(sum);

		}

}