블랙잭
시간제한 | 메모리제한 | 제출 | 정답 | 맞힌 사람 | 정답률 |
---|---|---|---|---|---|
1 초 | 128 MB | 182380 | 91332 | 69942 | 48.785% |
문제
카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.
한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.
김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.
이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.
N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.
입력
첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.
합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.
출력
첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.
예제 입력 1 복사
5 21
5 6 7 8 9
예제 출력 1 복사
21
예제 입력 2 복사
10 500
93 181 245 214 315 36 185 138 216 295
예제 출력 2 복사
497
알고리즘 분류
설명
블랙잭 문제를 해결하기 위해서는 주어진 카드 중에서 3장의 합이 M을 넘지 않으면서 최대한 M에 가까운 값을 찾아야 합니다. 이를 위해 브루트 포스 접근법을 사용할 수 있습니다.
브루트 포스 접근법에서는 모든 가능한 3장의 카드 조합을 확인하고, 조건에 맞는 최적의 조합을 찾습니다. 이 문제의 제약 조건(N이 최대 100)이 브루트 포스 접근법을 사용할 수 있을 정도로 적당히 작기 때문에 적합한 접근법입니다.
하나. 3중 루프를 사용하여 모든 가능한 3장의 카드 조합을 탐색합니다.
둘. 각 조합의 합을 계산하고, 이합이 M을 넘지 않으면서 지금까지 최대값보다 크다면 이 값을 업데이트합니다.
셋. 모든 조합을 탐색한 후, 최종적으로 저장된 최대값을 출력합니다.
//메모리 : 15744KB
// 시간 : 148MS
package 블랙잭;
import java.io.*;
import java.util.StringTokenizer;
/*
[시간 복잡도]
이 코드는 3중 for 루프를 사용하여 모든 가능한 3장의 카드 조합을 탐색합니다.
각 루프는 카드의 개수 N에 대해 실행됩니다.
- 첫 번째 for 루프는 N번 실행됩니다.
- 두 번째 for 루프는 첫 번째 루프의 각 반복마다 (N-1), (N-2), ..., 1번 실행됩니다.
- 세 번째 for 루프는 두 번째 루프의 각 반복마다 (N-2), (N-3), ..., 1번 실행됩니다.
결국: O(N^3) 시간 복잡도로 수렴합니다. 따라서 이 알고리즘의 시간 복잡도는 O(N^3)입니다.
### 결론
이 알고리즘은 N장의 카드에서 3장의 카드 조합을 모두 탐색하기 때문에 시간 복잡도는 O(N^3)입니다.
N이 최대 100이므로 최악의 경우 100^3 = 1,000,000번의 연산을 수행하게 됩니다.
이는 현대 컴퓨터에서는 충분히 처리 가능한 범위입니다.
따라서 이 알고리즘은 주어진 문제의 제약 조건 내에서 효율적으로 작동합니다.
*/
public class Main {
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N, M;
static int[] cards;
static int maxSum = 0; // max_sum 변수를 0으로 초기화합니다. M을 넘지 않으면서 최대한 가까운 3장의 카드 합을 저장하는 변수입니다.
public static void main(String[] args) throws IOException{
st = new StringTokenizer(br.readLine());
// 카드의 개수 N, 목표 숫자 M, 카드 목록 cards를 할당받고 초기화 하도록 합니다.
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
cards = new int[N];
st = new StringTokenizer(br.readLine());
// 2번째줄의 입력 버퍼 데이터를 cards int 배열에 할당합니다.
for(int i = 0; i < N; i++){
cards[i] = Integer.parseInt(st.nextToken());
}
// 3중 for문을 이용하여 모든 3장의 카드 조합을 확인
for(int i = 1; i < N; i++){
for(int j =i+1; j < N; j++){
for(int k =j+1; k < N; k++){
int cardSum = cards[i] + cards[j] + cards[k];
// 각 조합의 합을 계산하고, 그 합이 M을 넘지 않으면 maxSum 갱신합니다.
if(cardSum <= M)
maxSum = Math.max(maxSum, cardSum);
}
}
}
bw.write(maxSum + "\n");
bw.flush();
bw.close();
br.close();
}
}
'여러가지 > 알고리즘 & 자료구조' 카테고리의 다른 글
[백준] 좋은 암호 - 2061번 (0) | 2024.06.12 |
---|---|
[백준] 타임머신 - 1440번 (1) | 2024.06.12 |
완전탐색 & 시뮬레이션 - 1 (0) | 2024.06.12 |
[백준] 신기한 소수 찾기 - 2023번 (1) | 2024.06.10 |
[백준] 나이트의 이동 - 7562번 (1) | 2024.06.10 |