백준 2798 Java - 블랙잭
제목 : 블랙잭
문제
카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다.
카드의 합이 21 을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다.
블랙잭은 카지노마다 다양한 규정이 있다.
한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.
김정인 버전의 블랙잭에서는 각 카드에 양의 정수가 쓰여 있다.
그 다음, 딜러는 N 장의 카드를 모두 숫자가 보이도록 바닥에 놓는다.
그런 후에, 딜러는 숫자 M 을 크게 외친다.
이제 플레이어는 제한된 시간 안에 N 장의 카드 중에서 3 장의 카드를 골라야 한다.
블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M 을 넘지 않으면서, M 과 최대한 가깝게 만들어야 한다.
N 장의 카드에 써져 있는 숫자가 주어졌을 때,
M 을 넘지 않으면서 M 에 최대한 가까운 카드 3 장의 합을 구해 출력하시오.
입력
첫째 줄에 카드의 개수 N (3 <= N <= 100) 과, M (10 <= M <= 300,000) 이 주어진다.
둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000 을 넘지 않는 양의 정수이다.
합이 M 을 넘지 않는 카드 3 장을 찾을 수 있는 경우만 입력으로 주어진다.
예제 입력 및 출력
| 예제 입력 | 예제 출력 |
|---|---|
5 21 |
21 |
10 500 |
497 |
Brute Force 란 무엇일까?
가능한 모든 조합을 "전부" 결합하여, 결과에 대응하는 것을 의미한다.
사실 이 부분부터, 순열 (Sequence) 에 대한 이해와, 최대 근접 상황 시 행동 강령을 알아야 한다.
단계별로 풀어보기 순서대로 여기까지 왔다면, 사실상 이제부터가 시작이라고 생각이 들기도 한다.
먼저, 수학적인 의미에서의 집합까지 생각하지 말고,
우리가 이 문제에서 간단히 사용하게 될 집합의 개념 정도만 생각해보자 - 필자도 집합의 수학적인 개념은 잘 모른다.
- 3 장의 요소를 고른다.
- 순서는 상관이 없다. - (ex 5, 6, 7 or 6, 5, 7) 을 고르던, 집합은 동일하다.
- 같은 요소를 2 번 고를 수는 없다.
- 요소는 중첩되지 않지만, 점점 커지는 규칙을 가지고 있지는 않다.
사실상 문제 자체에서 "3개" 의 카드를 고르도록 정해져 있기 때문에,
아직 순열에서의 dfs 알고리즘을 사용 할 필요는 없다.
하지만, 동적 집합 개수에 대한 개념을 제외하더라도, 순서 상관이 없는 요소를 고르는 것을 고려해야 한다.
이 문제에 대한 해결법은 2 가지가 있다.
- 간단한 버전 - 직접 for or while 을 3 번 사용하여 브루트 포스 한다.
- 어렵지만, 곧 나오게 될 알고리즘을 미리 보게 될 dfs 방식
간단한 버전의 풀이법
문제에서 명시적으로 "3개" 의 카드를 선택하라고 했다.
이 경우, 우리는 for or while 을 선택하여 풀이하면 된다.
나는 for 을 사용하여 풀도록 하겠다 - while 과는 본질적으로 동일하므로.
그 전에, 순서 상관이 없다는 것을 프로그래밍적으로 어떻게 이해해야 할까?
한번 위의 입력 예제 5 6 7 8 9 에 대해서 3 개의 집합을 머릿속으로 만들어 보자.
| 1 번째 카드 | 2 번째 카드 | 3 번째 카드 | 중첩 여부 |
|---|---|---|---|
| 5 | 6 | 7 | x |
| 5 | 6 | 8 | x |
| 5 | 6 | 9 | x |
| 6 | 5 | 8 | o (2 번째 요소와 중첩됨) |
| ... | ... | ... | ... |
2 번째 레이블과, 4 번째 레이블은 중첩된다.
즉, 순서는 상관이 없다고 했으므로, (5, 6, 8) 이던, (6, 5, 8) 이던 동일하다는 것이다.
그렇다는 것은, (1번째 카드 인덱스) < (2번째 카드 인덱스) < (3번째 카드 인덱스) 를 의미한다.
우리는 입력 예제 5 6 7 8 9 에 대해서 1 차원 배열로 저장할 것이다.
- 1 번째로 고른 카드 인덱스
i에 대해서, 2 번째로 고른 카드 인덱스j를 순회한다. - 2 번째로 고른 카드 인덱스
j에 대해서, 3 번째로 고른 카드 인덱스k를 순회한다.
이를 구현하는 것이 이번 문제의 관건이다.
즉, (i < j < k) 이다. (순서 상관없으며, 요소가 중첩되지 않는 집합.)
이를 구현하기 위해서, 간단한 방식으로 for 문을 3 번 중첩하면 된다.
Answer 1 - for 문을 중첩
이 문제와 같이, 적은 숫자 만큼 요소를 뽑아 모든 경우의 수를 알아볼 때 사용하는 방식이다.
import java.io.*;
import java.util.*;
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());
// 딜러가 크게 외칠 숫자 - 3 개의 요소를 더했을 때, 가장 가까운 숫자를 구할 때 비교하게 됨.
int M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int[] cards = new int[N];
for(int i = 0; i < N; i++)
cards[i] = Integer.parseInt(st.nextToken());
// 3 개를 뽑으므로. - 초기화
int[] select = new int[3];
// 가장 큰 수 - 초기화
int max = -1;
for (int i = 0; i < N; i++) { // 1 번째 카드 선택
select[0] = cards[i];
for (int j = i + 1; j < N; j++) { // 2 번째 카드 선택
select[1] = cards[j];
for (int k = j + 1; k < N; k++) { // 3 번째 카드 선택
select[2] = cards[k];
// 현재 선택한 3 개의 카드에 대해서 총합을 계산한다.
int sum = select[0] + select[1] + select[2];
// 만약 딜러가 말한 숫자보다, 현재 3 개 카드의 합이 더 크면 안된다는 규칙이 있었다.
if (sum > M) {
// 무시하고, 다른 카드의 조합을 찾는다.
continue;
} else {
// 현재까지 저장하고 있는 최대 값 보다,
// 조합된 3 개의 카드 합이 더 크다면, 최대값을 최신화한다.
max = max < sum ? sum : max;
}
}
}
}
System.out.println(max);
}
}
밑의 풀이 방식은 좀 나중에 다뤄지게 되므로, 아직 접하지 않은 DFS 문제를 어떻게 풀어야 할지,
궁금한 사람들이 보면 된다. "재귀" 라는 의미에 대해서 알아야 하기 때문이다.
DFS 방식의 풀이법
혹시 "재귀" 라는 말을 들어 본 적이 있는가?
재귀 란, 자기 자신을 호출(사용) 하는 행동을 의미한다.
이에 대해서 자세한 내용은
를 참조하거나, 검색해 보길 바란다.
이 문제에서 재귀를 결합한다면, 우리가 dfs 메서드를 제작하며 고려해야 할 2 가지 요소가 있다.
- 재귀 코드에서, 자기 자신의 코드를 호출 할 때, 입력값은 서로 달라야 한다.
- 3 개의 요소를 선택하므로, 재귀의 깊이는
3이다.
import java.util.*;
import java.io.*;
public class Main {
// dfs 메서드에서 최대값을 업데이트 할 수 있도록 설정.
public static int max = -1;
// dfs 메서드에서 마지막 카드까지 골랐을 때, 규칙을 만족하는지 확인하기 위해.
public static int M;
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());
M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
// 주어진 모든 카드를 담을 장소(배열)
int[] cards = new int[N];
for(int i = 0; i < N; i++) {
cards[i] = Integer.parseInt(st.nextToken());
}
// 선택된 3 개의 카드를 담을 저장소
int[] select = new int[3];
dfs(0, cards, select, 0);
System.out.println(max);
}
static void dfs(int startIndex, int[] cards, int[] select, int deep) {
if(deep == 3) {
// 선택된 카드들에 대한 합
int tempResult = sum(select);
// 규칙을 지켰는지 확인하기 위해.
if(tempResult > M)
return;
max = max < tempResult ? tempResult : max;
// 3 개를 모두 선택했으므로, 밑의 로직은 실행하지 않는다. (IndexOutOfBounds 에러 예방)
return;
}
for(int i = startIndex; i < cards.length; i++) {
select[deep] = cards[i];
dfs(i + 1, cards, select, deep + 1);
}
}
static int sum(int[] select) {
int sum = 0;
for(int i = 0; i < select.length; i++)
sum += select[i];
return sum;
}
}메서드 재귀를 위해 따로 dfs(...) 함수를 제작했다.
사실 여기서 int[] cards, int[] select 두 개의 메서드 인자는 정적 변수로 선언해도 된다.
하지만, 재귀를 특성을 더 돋보이기 위해, 인자로 넣었다.
한번 dfs 메서드 내부의 인자의 의미를 살펴보자 :
startIndex: 순서를 상관하지 않는 집합의 특성으로, 이전에 이미 선택되었던 카드는 신경 쓸 필요가 없다.int[] cards: 주어진 모든 카드의 정보를 담아두는 배열int[] select: 선택한 카드의 정보를 저장하는 배열int deep: 현재 선택할 카드의 순서를 저장하는 숫자. (0,1,2)deep이3이 된다면,select배열이 모두 채워졌다는 의미이므로, 계산을 수행 할 시간이라는 뜻.