[백준알고리즘-JAVA]2798번 풀이(블랙잭) - 초보도 이해하는 풀이

안녕하세요

인포돈입니다.

백준 알고리즘 2798번 풀이입니다. 


* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 2798 (블랙잭)

 

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 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장의 합을 출력한다.

입력 예시

5 21
5 6 7 8 9

출력 예시

21

입력 예시

10 500
93 181 245 214 315 36 185 138 216 295

출력 예시

497

성공코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class test {
	
	public static void main(String args[]) throws IOException{
	   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   	 
	   	String[] str = br.readLine().split(" ");
	   	String[] str1=br.readLine().split(" ");
	   	 	
	   	int sum = 0;
	   	 	
	   	for(int i = 0 ; i < str1.length-2 ; i++) {
	   	 for(int j = i+1; j <str1.length; j++ ) {
	   	 	for(int k = j+1; k < str1.length ; k++) {
	   	 	if( Integer.parseInt(str[1]) >= (Integer.parseInt(str1[i])+Integer.parseInt(str1[j])+Integer.parseInt(str1[k]))) {
	   	 	if(sum <= (Integer.parseInt(str1[i])+Integer.parseInt(str1[j])+Integer.parseInt(str1[k])))
	   	 	sum = (Integer.parseInt(str1[i])+Integer.parseInt(str1[j])+Integer.parseInt(str1[k]));
	   	 			}
	   	 			}
	   	 		}	
	   	 	}
	   	 		   		
	   		System.out.println(sum);

 

 블랙잭 알고리즘의 카테고리는 브루트 포스의 카테고리로 분류가 됩니다. 이는 작은 힌트가 될 수 있는데요!  바로 일련의 문자열을 하나씩 대입해보는 암호학의 일종인 브루트 포스 계열의 문제라면, 이전에 생각했던 알고리즘처럼 수학적으로 식을 내리는 게 아니라 하나씩 대입해보는 문제임을 유추해 볼 수 있습니다!

 

이점을 고려하여 저희는 해당 STEP을 따라가 보며, 누구라도 쉽게 이해할 수 있도록 코드를 설명해드릴게요 ~

---

알고리즘 흐름도

입력받기 -> 받음 입력을 통해 가장 가까운 값의 합을 출력

 

.. 알고리즘 흐름도가 너무 짧아 보이는데 이이상 설명은 너무 복잡해질 수 있다고 생각합니다! 바로 STEP으로 넘어가 봅시다 ~

---

STEP1 받은 입력을 분류해서 넣어주기

블랙잭 알고리즘은 입력받을 것이 많습니다 ㅜㅜ 그래서 저희는 구분을 잘해 주어야 합니다.

저는 일단 기본적으로 bufferedreader를 통해 받아온 값을 split(" ") 공백을 기준으로 불리하여 문자열 배열에 넣어주었습니다.

그렇다면 윗줄에 적힌 입력은 str 아랫줄에 적힌 입력은 str1에 저장이 되게 됩니다.

 

이제 초보도 쉽게 이해할 수 있게 첫 번째 예시로 알려드리겠습니다.

 

str [0] = 5

str [1] = 21

str1 [0] = 5

str1 [1] = 6

str1 [2] = 7

str1 [3] = 8

str1 [4] = 9

 

이런 식으로 값들이 들어가게 됩니다.

---

STEP2 값을 일일이 더해주는 반복문 만들어보기

자 문제에서 주어진 것은 아무리 많은 카드가 있더라도 저희는 딱 3장의 카드가 필요합니다.!

 

이 3장을 어떤 식으로 구분을 해야 할까요?

 

 0 0 0 0 0

 1 1 1 - -

 

 0 0 0 0 0

 1 1 - 1 -

 

 0 0 0 0 0

 1 1  - -  1

 

 0 0 0 0 0

 1  - 1 1 -

 

이런 식으로 3장의 카드를 일련의 규칙대로 더해주면 되지 않을까요?

이런 식으로 진행을 해보면 마지막은 결국

 

 0 0 0 0 0

 -  - 1 1 1

 

이런식으로 마지막 3장까지의 합을 구할 수 있게 되죠

 

이를 for문으로 구분해볼게요 

for(int i = 0 ; i < str1.length-2 ; i++) {
	   	 		for(int j = i+1; j <str1.length; j++ ) {
	   	 			for(int k = j+1; k < str1.length ; k++) {
	   	 				}
	   	 			}
	   	 		}	
	   	 	

해당 코드를 어떻게 생각하냐고요?

ㅎㅎ i는 바로 첫 번째 숫자

j는 두 번째 숫자,

k는 세 번째 숫자로 생각해보시면 쉽게 해결할 수 있습니다. 각자의 자리에서 +1을 해주어 옆자리임을 알려주게 되죠.

 

왜냐하면 저희는 해당 숫자들을 str1에 배열의 형태로 저장해 주었기 때문입니다!

 

---

STEP 3 어떠한 숫자의 합일 때 결과 값에 값을 넣어줄지 결정하기

 

이제 3자리의 합을 표현할 수 있게 되었다면, 그 합들 중에 어떠한 값이 str [1]에 들어있는 값과 가장 가까울까요?

 

자 만약에 5 6 7 의숫자의 합이라고 생각해 봅시다. 그러면 18의 숫자가 나오죠 그럼 21과 3의 차이가 나게 돼 죠. 만약에 이 차가 0이라면 해당 숫자와 가장 가까운 수가 되겠죠 ㅎㅎ

 

 

그런데 그러면 만약에 22가 나오면 차가 -1인데 어떻게 해요?라고 생각하시는 분이 있을 수 있습니다.

 

바로 절댓값을 사용하는 것입니다. 이전에 배웠던 Math에 abs함수를 이용해 절댓값을 쉽게 출력할 수 있죠.

 

if( Integer.parseInt(str[1]) >= (Integer.parseInt(str1[i])+Integer.parseInt(str1[j])+Integer.parseInt(str1[k]))) {
if(sum <= (Integer.parseInt(str1[i])+Integer.parseInt(str1[j])+Integer.parseInt(str1[k])))
sum = (Integer.parseInt(str1[i])+Integer.parseInt(str1[j])+Integer.parseInt(str1[k]));
}

해당 코드가 길어 보이실 수 있는데 간단합니다.

 

위에 if문은 문제에서 주어진 것처럼 str [1]의 값을 넘어가면, 넣어주지 말라는 의미이죠

 

즉 이런 식의 조건이 있다면, 굳이 abs를 사용하지 않고 해당 값을 넣어주면 되죠.

 

두 번째 if문은 3개의 합이 기존에 있던 sum보다 크거나 같다면 그 값을 sum에 넣어주게 되죠.

 

왜냐하면, 첫 번째 if문에서 이미 str [1]보다 큰 값들을 걸러줬기 때문에 해당 작업만으로도 가장 21에 가까운 값을 뽑아낼 수 있게 됩니다.

---

해당 STEP을 잘 따라오면 해당 알고리즘 문제는 쉽게 풀이할 수 있음을 알 수 있습니다 ~