[백준] 2798: 블랙잭

1927번: 최소 힙

내 코드

import java.util.*;

public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);

		int num = sc.nextInt();
		int max = sc.nextInt();
		int result = 0;

		ArrayList<Integer> list = new ArrayList<>();

		for(int i = 0; i < num; i++) {
		    int n = sc.nextInt();
		    list.add(n);
		}

		for(int i = 0; i < list.size(); i++) {
		    int ele1 = list.get(i);
		    for(int j = i + 1; j < list.size(); j++) {
		        int ele2 = list.get(j);
		        for(int k = j + 1; k < list.size(); k++) {
		            int ele3 = list.get(k);
		            int sol = ele1 + ele2 + ele3;
		            if(sol <= max && sol > result) {
		                result = sol;
		            }
		        }
		    }
		}

		System.out.print(result);

        
	}
}

문제와 관련된 개념

브루트 포스 (Brute Force)

어떤 값을 찾아내기(또는 목적을 달성하기) 위해 무차별적으로 대입해보는 방법.

 

이 알고리즘의 가장 큰 특징은 가능한 모든 경우의 수를 대입해보며 조건에 만족하는 값만을 찾아낼 수 있다는 점이다.
결국 자원만 충분하다면 원하는 값을 100% 확률로 찾아낼 수 있다는 것이 매우 크다.

 

특히나 암호학에서 위 방법은 매우 원초적일 수 있으나 정확도가 100% 이다보니 자원이 무한하면 가장 무서운 방법이기도 하다.
그렇기에 브루트 포스 알고리즘을 위해 가장 중요한 것은 "빠짐 없이" 완전탐색 알고리즘을 잘 짜야한다는 점이다.

 

출처
[백준] 2798번 : 블랙잭 - JAVA [자바]

문제 풀이

n번 반복하는 반복문을 통해 n번의 입력값을 받는다. 그 후

1) 입력값이 0이면 1-1) 큐가 비어있는 경우 0을 출력하고, 1-2) 그렇지 않은 경우 큐의 수를 출력한다.
2) 입력값이 0이 아닌 경우 2-1) 우선순위 큐에 입력값을 더해준다.

Trouble Shooting

처음에 for문 내부 if 문에서 절댓값을 통해 아래와 같이 비교하고자 하였으나, 에러가 발생하였다.
if(Math.abs(max-sol) < Math.abs(max-result))
따라서 절댓값이 아닌, max와 result 변수의 값을 이용하여 구하는 것으로 변경하였다.
if(sol <= max && sol > result)

느낀점

3중 for 문을 사용하여 풀었는데, 이보다 간단한 방법으로 풀 수 있지 않을까?라는 아쉬움이 많이 남는다.