백준 2798번: 블랙잭 (java)
2021. 8. 24. 14:45ㆍAlgorithm/백준
여러 풀이 방법이 있지만 나는 조합으로 풀었다. N개의 카드중에 3개의 카드를 순서 없이 뽑아 더해주어 M 보다 작으면서 가장 큰 값을 출력 해주면 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
// 백준 2798번
public class Baekjoon_블랙잭 {
static int N, R = 3; // 전체 N장의 카드 전체 N개중에 3개를 뽑는 조합.
static int M; // M 의 합을 넘기지 않는 수
static int[] arr; // arr 배열에 N장의 카드 담기
static int[] numbers; // 3장의 뽑은 카드를 넣을 배열
static int res;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N];
st = new StringTokenizer(in.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
numbers = new int[R];
combi(0, 0);
System.out.println(res);
}
private static void combi(int cnt, int start) {
int sum = 0;
// 종료조건
if (cnt == R) {
for (int i = 0; i < numbers.length; i++) {
sum += numbers[i];
}
if(sum <= M) {
res = Math.max(res, sum);
}
return;
}
// start 위치의 수부터 가능한 수를 모두 고려
for (int i = start; i < N; i++) { // i : 인덱스
numbers[cnt] = arr[i]; // 있는 수를 집어넣고
// 다음 자리 조합 뽑으러간다.
combi(cnt + 1, i + 1);
}
}
}
728x90
'Algorithm > 백준' 카테고리의 다른 글
백준 10163번 : 색종이 (java) (0) | 2021.08.25 |
---|---|
백준 11399번: ATM (java) (0) | 2021.08.24 |
백준 1592번: 영식이와 친구들 (java) (0) | 2021.08.22 |
백준 2567번: 색종이 - 2 (java) (0) | 2021.08.22 |
백준 2804번: 크로스워드 만들기 (java) (0) | 2021.08.22 |