https://www.acmicpc.net/problem/2798
2798번: 블랙잭
첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장
www.acmicpc.net
알고리즘 - 브루트 포스
정의
- 난폭한(무식한) 힘
- 무차별적 대입 방법
특징
- 가능한 모든 경우의 수 대입 ➡ 조건에 만족하는 값만을 찾아냄
- 자원만 충분하다면 원하는 값을 100% 확률로 찾을 수 있음
- "빠짐 없이" 완전탐색 알고리즘을 잘 설계하는 게 핵심
풀이
1. Scanner
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int M = in.nextInt();
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = in.nextInt();
}
int result = search(arr, N, M);
System.out.println(result);
}
//탐색
static int search(int[] arr, int N, int M) {
int result = 0;
//카드 3개 뽑기 - 첫 번째 카드 : N - 2 까지 순회
for (int i = 0; i < N - 2; i++) {
//카드 2개 뽑기 - 두 번째 카드 : 첫 번째 카드 다음부터 N - 1 까지 순회
for (int j = i + 1; j < N - 1; j++) {
//카드 1개 뽑기 - 세 번째 카드 : 두 번째 카드 다음부터 N 까지 순회
for (int k = j + 1; k < N; k++) {
//3개 카드의 합
int temp = arr[i] + arr[j] + arr[k];
//M = 세 카드의 합 ➡ temp 반환 및 종료
if (M == temp) {
return temp;
}
//이전의 합 < 세 카드의 합 < M ➡ result 갱신
if(result < temp && temp < M) {
result = temp;
}
}
}
}
//모든 순회 마치면 result 반환
return result;
}
}
2. BufferedReader + StringTokenizer
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 M = Integer.parseInt(st.nextToken());
int[] arr = new int[N];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int result = search(arr, N, M);
System.out.println(result);
}
//탐색
static int search(int[] arr, int N, int M) {
int result = 0;
//카드 3개 뽑기 - 첫 번째 카드 : N - 2 까지 순회
for (int i = 0; i < N - 2; i++) {
//카드 2개 뽑기 - 두 번째 카드 : 첫 번째 카드 다음부터 N - 1 까지 순회
for (int j = i + 1; j < N - 1; j++) {
//카드 1개 뽑기 - 세 번째 카드 : 두 번째 카드 다음부터 N 까지 순회
for (int k = j + 1; k < N; k++) {
//3개 카드의 합
int temp = arr[i] + arr[j] + arr[k];
//M = 세 카드의 합 ➡ temp 반환 및 종료
if (M == temp) {
return temp;
}
//이전의 합 < 세 카드의 합 < M ➡ result 갱신
if(result < temp && temp < M) {
result = temp;
}
}
}
}
//모든 순회 마치면 result 반환
return result;
}
}3. Scanner + 조건문
- 첫 번째 카드가 M보다 크거나
- 두 번째 카드까지 선택 시 두 카드의 합이 M보다 크다면
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int M = in.nextInt();
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = in.nextInt();
}
int result = search(arr, N, M);
System.out.println(result);
}
//탐색
static int search(int[] arr, int N, int M) {
int result = 0;
//카드 3개 뽑기 - 첫 번째 카드 : N - 2 까지 순회
for (int i = 0; i < N - 2; i++) {
//첫 번째 카드 > M ➡ skip
if(arr[i] > M) {
continue;
}
//카드 2개 뽑기 - 두 번째 카드 : 첫 번째 카드 다음부터 N - 1 까지 순회
for (int j = i + 1; j < N - 1; j++) {
//첫 번째 카드 + 두 번째 카드 > M ➡ skip
if(arr[i] + arr[j] > M) {
continue;
}
//카드 1개 뽑기 - 세 번째 카드 : 두 번째 카드 다음부터 N 까지 순회
for (int k = j + 1; k < N; k++) {
//3개 카드의 합
int temp = arr[i] + arr[j] + arr[k];
//M = 세 카드의 합 ➡ temp 반환 및 종료
if (M == temp) {
return temp;
}
//이전의 합 < 세 카드의 합 < M ➡ result 갱신
if(result < temp && temp < M) {
result = temp;
}
}
}
}
//모든 순회 마치면 result 반환
return result;
}
}
4. BufferedReader + StringTokenizer + 조건문
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 M = Integer.parseInt(st.nextToken());
int[] arr = new int[N];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int result = search(arr, N, M);
System.out.println(result);
}
//탐색
static int search(int[] arr, int N, int M) {
int result = 0;
//카드 3개 뽑기 - 첫 번째 카드 : N - 2 까지 순회
for (int i = 0; i < N - 2; i++) {
//첫 번째 카드 > M ➡ skip
if(arr[i] > M) {
continue;
}
//카드 2개 뽑기 - 두 번째 카드 : 첫 번째 카드 다음부터 N - 1 까지 순회
for (int j = i + 1; j < N - 1; j++) {
//첫 번째 카드 + 두 번째 카드 > M ➡ skip
if(arr[i] + arr[j] > M) {
continue;
}
//카드 1개 뽑기 - 세 번째 카드 : 두 번째 카드 다음부터 N 까지 순회
for (int k = j + 1; k < N; k++) {
//3개 카드의 합
int temp = arr[i] + arr[j] + arr[k];
//M = 세 카드의 합 ➡ temp 반환 및 종료
if (M == temp) {
return temp;
}
//이전의 합 < 세 카드의 합 < M ➡ result 갱신
if(result < temp && temp < M) {
result = temp;
}
}
}
}
//모든 순회 마치면 result 반환
return result;
}
}성능
- BufferedReader > Scanner
'Algorithm > Baekjoon' 카테고리의 다른 글
| [백준] 7568번 : 덩치 - Java (0) | 2022.04.26 |
|---|---|
| [백준] 2231번 : 분해합 - Java (0) | 2022.04.12 |
| [백준] 11729번 : 하노이 탑 이동 순서 - Java (0) | 2022.04.07 |
| [백준] 2447번 : 별 찍기 - 10 - Java (0) | 2022.04.06 |
| [백준] 10870번 : 피보나치 수 5 - Java (0) | 2022.04.05 |
댓글