[Java] 백준 2798 블랙잭

2798번: 블랙잭

블랙잭

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초

128 MB

164859

81996

62746

48.515%

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 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️⃣ 문제 분석하기

• N장의 카드를 숫자가 보이게 바닥에 놓는다
• 그 후 숫자 M을 외친다.
• 그 후 N장의 카드중에서 3장의 카드를 고른다.
• 3장의 카드는 M보다 작거나 같으면서, M에 최대한 가까운 카드 3장의 합을 구해 출력하기.

2️⃣ 요구 조건 구현하기

• Bufferedreader 생성
• StringTokenizer 생성
• int N = Bufferedreader 입력 받기.
• 배열 생성 후 배열을 for문으로 입력받기
• Array 함수를 이용해서 오름차순 정렬을 한다.
• for문을 돌려서 조건을 주며 최종적으로 출력한다.

3️⃣ 슈도 코드

Bufferedreader br = new Bufferedreader(inputsteream(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());

int N =StringTokenizer입력
int M =StringTokenizer입력

int[] arr1 = new int[N];
StringTokenizer  = Bufferedreader 입력받기

for문 {

  arr1[i] = st .nextToken();
}

배열 정렬하기
sum 변수 생성

//투 포인터 알고리즘 적용
for문() {
	자세한건 아래 코드 보기.
}

sum 출력

 

4️⃣ 코드 작성

package 알고리즘;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class B2798 {
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(bf.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int[] arr = new int[N];

		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr);

		int result = 0;

		for (int i = 0; i < N - 2; i++) {
			int min = i + 1;
			int max = N - 1;

			while (min < max) {
				int sum = arr[i] + arr[min] + arr[max];

				if (sum <= M) {
					result = Math.max(result, sum);
					min++;
				} else {
					max--;
				}
			}
		}

		System.out.println(result);
	}
}

• 위 알고리즘에서 투 포인터 알고리즘을 적용하기 위해
  • Arrays.sort를 사용해 입력받은 수를 오름차순 정렬을 합니다.
• why 조건을 이렇게 줬나요?

		for (int i = 0; i < N - 2; i++) {
			int min = i + 1;
			int max = N - 1;

			while (min < max) {
				int sum = arr[i] + arr[min] + arr[max];

				if (sum <= M) {
					result = Math.max(result, sum);
					min++;
				} else {
					max--;
				}
			}
		}

• 간단하게 예를 다시 들어보자 N은 5이고 M이 21이라고 가정
  • 배열안에 숫자는 그럼 [ 5,6,7,8,9 ] 라고 가정 ( -> 정렬을 한 이후 값임)
• 🖐 i=0 일 경우 (=첫번째 카드 먼저 선택할 경우)
  • i=0 일 때 첫번째 카드는 5 이다. 나머지 두 카드도 선택을 해야한다.
  • 선택을 하는 기준은 우리가 정렬을 해두었기 때문에, 왼쪽기준으로 작은수부터 높은 숫자순으로 올라가게 될 것이다.
  • 그러므로 첫번째 카드 선택시
    • 두번째 카드는 i+1 선택
      • 세번째 카드는 맨 마지막 N-1을 한 카드를 뽑는다
        • 왜 세번째는 i가 아니라 N이냐면은, 위 for문은 배열의 길이 즉N만큼 설정되어 있기 때문에 이 배열의 마지막은 N과 같다 ,

 

• 🖐i=1 일 경우 (=두 번째 카드를 먼저 선택할 경우)
  • **i = 1**일 때, 첫 번째 카드는 6입니다. 나머지 두 카드를 선택해야 하므로, **left**는 **i + 1**인 7이 되고, **right**는 **N - 1**인 8가 됩니다.
  • **left**와 **right**를 조절하면서 합을 계산합니다. (6, 7, 8)는 합이 21이므로, 결과를 업데이트합니다.
  • 여기서 만약 조건을 다 돌아보고 가장 가까운 값을 출력한다.
  • 모든 경우의수를 다 체크해야함으로 시간복잡도가 복잡함.

 

• Math에 max 함수는 두 값중에서 더 큰값을 반환한다.
  • result, sum 둘중에서 더 M에 가까운 값을 출력한다고 생각하면 된다.
  • result는 현재까지의 최대 합
  • sum은 현재 검사중인 세 카드의 합이다.

 

5️⃣ 핵심 파악하기

• 투포인터 알고리즘 파악하기