백준 2798번 블랙잭 자바 Java / 11단계 브루트 포스

백준 11단계 1번 문제 - 2798 블랙잭

https://www.acmicpc.net/problem/2798

2798번: 블랙잭

 

 

 

---

11. 브루트 포스 (1) 백준 2798번 문제 블랙잭

---

문제

---

 

 

 

 

 

---

과정 생각해보기

---

 

우선 들어가기 전에, 11단계 처음 문제이니 11단계 <브루트 포스>가 뭔지 알고 넘어가야 했다

‘브루트 포스(Brute Force)’는 조합 가능한 모든 경우의 수를 다 대입해보는 것이다. 최적화나 효율과는 거리가 멀다. 단순한 방법으로 보이기도 하지만 사실 정확도 100%를 자랑한다. 이론적으로 모든 가능한 수를 점검해 보니 실수가 없다. 암호학에서도 가장 확실한 방법으로 통하는 이유다. 완벽한 병렬 작업이 가능한 것도 장점이다. 

[네이버 지식백과] 브루트 포스 공격 [Brute Force Attack] (ICT 시사상식 2017, 2016.12.20)

 

말그대로 하나하나 다 대입해보는 방식이다

 

이 문제는 숫자 n개, 만들어야 할 숫자 m, n개의 숫자 목록이 주어질 때

목록 중 3개를 합쳐 m보다 크지 않으면서 가장 가까운 숫자(즉, <= m)를 만들어내는 것이다 

 

 

 

---

오답

---

 

오답까지는 아니고, 비효율적으로 메인메서드 안에서 해결하려는 코드를 짰다

반복문을 만들 때, 가장 바깥에 있는 건 n-2까지 돌아야한다는 걸 생각해내는 게 조금 어려웠다

 

 

 

---

정답 인정 코드

---

 

https://st-lab.tistory.com/97

이 블로그를 참고했다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
        
        st = new StringTokenizer(br.readLine());
        int arr[] = new int[n];
        
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int answer = Blackjack(arr, n, m);
        System.out.println(answer);
    }
    
    static int Blackjack (int[] arr, int n, int m) {
        int answer = 0;
        int tmp = 0;
        for(int i = 0; i < n-2; i++) {    //처음부터 n-2(j, k가 반복해줄 부분)
            
            if(arr[i] > m) continue;    //첫 번째 카드가 m보다 크면 넘어간다
            
            for(int j = i+1; j < n-1; j++) {    //두번째부터 n-1(마지막은 k)
                
                if(arr[i] + arr[j] > m) continue; //처음+두번째 합이 m보다 크면 넘어간다
                
                for(int k = j+1; k < n; k++) {
                    tmp = arr[i] + arr[j] + arr[k];
                
                    if(m == tmp) {
                        return tmp;
                    }
                
                    if(answer < tmp && tmp < m) {
                        answer = tmp;
                    }
                }
            }
        }
        return answer;
    }
}

 

메서드로 분리하는 것과 continue로 제끼는 조건까지 만든다는 점이 나와 달랐다

 

 

 

---

직후 백지 복습

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
        
        st = new StringTokenizer(br.readLine());
        int arr[] = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int answer = Blackjack(arr, n, m);
        System.out.println(answer);
    }
    
    static int Blackjack(int[] arr, int n, int m) {
        int answer = 0;
        int tmp = 0;
        
        for(int i = 0; i < n-2; i++) {
            if(arr[i] > m) continue;
            for(int j = i+1; j < n-1; j++) {
                if(arr[i]+arr[j] > m) continue;
                for(int k = j+1; k < n; k++) {
                    tmp = arr[i] + arr[j] + arr[k];
                    
                    if(m == tmp) {
                        return tmp;
                    }
                    
                    if(answer < tmp && tmp < m) {
                        answer = tmp;
                    }
                }
            }
        }
        return answer;
    }
}

 

틀린 건 없었다

 

 

 

---

단계적으로 풀어보기를 하면서 특히 반복문을 더 정확히 이해하게 되는 것 같다