백준 2798번 자바 문제 답/해설(블랙잭 문제)

[1] 백준 카테고리

단계별로 풀어보기

브루트 포스

1단계 10870번 문제

블랙잭

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

2798번: 블랙잭

 

[2] 문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

 

1. 입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

 

2. 출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

 

3. 예제 입력 1

5 21
5 6 7 8 9

 

4. 예제 출력 1

21

 

[3] 정답

1. 정답 해설 미포함

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
 
	public static void main(String[] args) throws IOException {
 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int n = Integer.parseInt(st.nextToken());
		int Max = Integer.parseInt(st.nextToken());
 
		int[] card = new int[n];
 
		st = new StringTokenizer(br.readLine(), " ");
		
		for (int i = 0; i < n; i++) {
			card[i] = Integer.parseInt(st.nextToken());
		}
		
		int result = black(card, n, Max);
		System.out.println(result);
	}
 
	
	static int black(int[] card, int n, int Max) {
		int result = 0;
 
		for (int i1 = 0; i1 < n - 2; i1++) {
						
			for (int i2 = i1 + 1; i2 < n - 1; i2++) {
 				
				for (int i3 = i2 + 1; i3 < n; i3++) {
					
					int temp = card[i1] + card[i2] + card[i3];
					
					if (Max == temp) {	
						return temp;
					}
					
					if(result < temp && temp < Max) {
						result = temp;
					}
				}
			}
		}
		
		return result;
	}
}

 

2.정답 해설 포함

import java.io.BufferedReader;
/* BufferedReader 사용을 위해서 java.io.BufferedReader 클래스를 import 한다.
Enter를 경계로 인식하고 받은 데이터는 String으로 고정된다.*/
import java.io.InputStreamReader;
/* byte 단위 데이터를 문자 단위 데이터로 처리할 수 있도록 변환해주기 위해서
InputStreamReader를 사용한다.
InputStreamReader 사용을 위해서 java.io.InputStreamReader 클래스를 import 한다.*/
import java.io.IOException;
/* 예외 처리를 위해서 IOException를 사용한다.
IOException 사용을 위해서 java.io.IOException 클래스를 import 한다.*/
import java.util.StringTokenizer;
/* 공백 단위로 호출하기 위해서 StringTokenizer를 사용한다
StringTokenizer를 사용하기 위해서
StringTokenizer java.util.String 클래스를 import 한다.*/

public class Main {
// 접근제어자 public으로 Main 클래스를 선언한다.

	public static void main(String[] args) throws IOException {
	/* 접근제어자 public으로 메모리에 상주하게 리턴값이 없이 main 함수를 선언한다.
	예외처리로 IOException를 포함한다.*/
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// BufferedReader 객체 br를 선언한다
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		// String 객체 st를 선언한다 이제 공백으로 값을 입력받을 수 있다.
		
		int n = Integer.parseInt(st.nextToken());
		// 변수 n에 값을 공백 단위로 구분해서 입력받는다.
		int Max = Integer.parseInt(st.nextToken());
		// 변수 Max에 값을 공백 단위로 구분해서 입력받는다.

		int[] card = new int[n];
		// int형 배열 card를 선언한다.

		st = new StringTokenizer(br.readLine(), " ");
		// 입력받는 값 사이에 개행을 넣는다.
		
		for (int i = 0; i < n; i++) {
		// for문을 선언한다. i가 0~<n까지 반복된다.
			card[i] = Integer.parseInt(st.nextToken());
			// 변수 card[i]에 값을 입력받는다.
		}
		
		int result = black(card, n, Max);
		// 함수 black를 호출하고 결과값을 int형 변수 result에 저장한다.
		System.out.println(result);
		// 변수 result에 저장된 값을 출력한다.
	}
 
	
	static int black(int[] arr, int n, int Max) {
	// 메모리에 상주하게 함수 black를 선언한다.
		int result = 0;
		// 변수 result를 선언한다.
		
		for (int i1 = 0; i1 < n - 2; i1++) {
		// 변수 i1 값이 0 ~ <n-2까지 괄호안의 코드가 반복된다.	
			
			for (int i2 = i1 + 1; i2 < n - 1; i2++) {
			// 변수 i2 값이 i1+1 ~ <i2까지 괄호 안의 코드가 반복된다. 
				for (int i3 = i2 + 1; i3 < n; i3++) {
				//변수 i3 값이 i2+1 ~ <n까지 괄호안의 코드가 반복된다.
				
					int temp = card[i1] + card[i2] + card[i3];
					// 변수 temp를 선언하고 오른쪽 연산 값을 저장한다.
					
					if (Max == temp) {
					// if문 선언 만약 Max값과 temp 값이 같으면
						return temp;
						// temp값을 리턴한다.
					}
					
					if(result < temp && temp < Max) {
					// result<temp 이면서 temp<Max 이면
						result = temp;
						// result 값에 temp 값을 저장한다.
					}
				}
			}
		}
		
		return result;
		// result 값을 리턴한다.
	}
}

 

존재하는 모든 카드를 다 더한 값을 최대로 나올 수 있는 수와 비교해 보면 된다. 코드로 나타내면

	static int black(int[] card, int n, int Max) {
		int result = 0;
 
		for (int i1 = 0; i1 < n - 2; i1++) {
						
			for (int i2 = i1 + 1; i2 < n - 1; i2++) {
 				
				for (int i3 = i2 + 1; i3 < n; i3++) {
					
					int temp = card[i1] + card[i2] + card[i3];
					
					if (Max == temp) {	
						return temp;
					}
					
					if(result < temp && temp < Max) {
						result = temp;
					}
				}
			}
		}

이 부분이 된다.

1번째 카드 + 2번째 카드 + 3번째 카드 값을 최대로 나올 수 있는 값과 비교

1번째 카드 + 2번째 카드 + 4번째 카드 값을 최대로 나올 수 있는 값과 비교

1번째 카드 + 2번째 카드 + 5번째 카드 값을 최대로 나올 수 있는 값과 비교.........

 

1번째 카드 + 3번째 카드 + 4번째 카드 값을 최대로 나올 수 있는 값과 비교

1번째 카드 + 3번째 카드 + 5번째 카드 값을 최대로 나올 수 있는 값과 비교

1번째 카드 + 3번째 카드 + 6번째 카드 값을 최대로 나올 수 있는 값과 비교...........

 

2번째 카드 + 3번째 카드 + 4번째 카드 값을 최대로 나올 수 있는 값과 비교

2번째 카드 + 3번째 카드 + 5번째 카드 값을 최대로 나올 수 있는 값과 비교

2번째 카드 + 3번째 카드 + 6번째 카드 값을 최대로 나올 수 있는 값과 비교.........

이런식으로 존재하는 모든 카드를 비교하고

만약 최대값이 나온다면 비교를 중단하는 것이다.

전에 더한 값보다 현재 더한 값이 크면서 현재값이 최대로 나올 수 있는 값보다 작다면 저장된 값이 현재 값으로 교체되게 된다.

 

[3] 결과