1. 문제 및 조건
문제
블랙잭은 카드의 합이 21이 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다.
N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.
입력
첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다.
둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.
합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.
출력
M을 넘지 않으면서 M에 가까운 카드 3장의 합을 출력한다.
2. 설명
해당 문제는 블랙잭 조건을 활용해 변형한 문제로, N개의 카드에서 3장의 합이 M보다 작은 것 중에서 최대값을 구하는 문제입니다. 정확한 최대값을 구하기 위해서는 때론 무식한 방법이 최선인 경우가 있습니다. 이 때 사용하는 방법이 브루트포스(Brute force) 입니다.
브루트포스란 영어 그대로 번역하면 "난폭한 힘"이라는 의미로, 자원(시간, 메모리 등)을 무식하게 사용해 원하는 값을 찾는 완전 탐색 알고리즘입니다. 이론적으로 가능한 모든 경우의 수를 다 탐색하는 것이기 때문에 원하는 값을 100% 찾을 수 있다는 장점이 있지만, 복잡한 문제에 해당 알고리즘을 적용할 경우 어마어마한 메모리 사용과 시간 낭비를 초래하기 때문에 가려 쓸 필요는 있습니다.
3. 해결 방식
M의 범위가 10 ≤ M ≤ 300,000이기 때문에, 3개의 카드를 고를 경우 최소값은 30이므로 30이하의 값을 현재 상태의 최댓값으로 지정합니다. (개인적으로는 0이 편해서 0으로 설정했습니다.)
첫 번째 카드를 고릅니다. 1 ~ N-2범위의 카드를 선택합니다.
두 번째 카드를 고릅니다. 첫 번째 카드의 다음 카드부터 N-1까지의 카드를 선택합니다.
세 번째 카드를 고릅니다. 두 번째 카드의 다음 카드부터 N까지의 카드를 선택합니다.
세 카드를 모두 선택해서 합을 구합니다. 구한 값이 M보다 큰 경우는 검사하지 않습니다. M보다 작은 경우는 현재 최댓값과 세 카드의 합을 비교해, 현재 최댓값이 세 카드의 합보다 작을 경우 최댓값을 변경합니다.
모든 반복이 종료되었을 경우 최종 최댓값을 반환합니다.
4. 코드
import java.util.Scanner;
class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String line1 = sc.nextLine();
int N = Integer.parseInt(line1.split(" ")[0]);
int M = Integer.parseInt(line1.split(" ")[1]);
String line2 = sc.nextLine();
int[] cards = new int[N];
for(int i=0;i<N;i++){
cards[i] = Integer.parseInt(line2.split(" ")[i]);
}
sc.close();
System.out.println(blackjeak(cards, M));
}
private static int blackjeak(int[] cards, int M){
int max = 0;
for(int i=0;i<cards.length-2;i++){
for(int j=i+1;j<cards.length-1;j++){
for(int k=j+1;k<cards.length;k++){
int value = cards[i]+cards[j]+cards[k];
if(value <= M && max < value) max = value;
}
}
}
return max;
}
}
Comentários