[백준 온라인저지]블랙잭 - 브루트포스(1)

블랙잭

이번 포스팅 문제는 2798번 문제입니다. 이 문제는 브루트포스 알고리즘을 이용하여 풀어냈습니다. 

브루트포스 알고리즘이란 모든 경우의 수를 구한 다음 그 중 최적의 해를 찾아내는 접근 방법입니다. 

그럼 문제를 풀어보도록 하겠습니다.

문제요약

n개의 카드 중 3개의 합을 구하는데 정수 m을 넘지않는 최대값을 구하는 문제입니다.

풀이전략

01. n개의 카드중 3개를 추출하는 모든 경우의 수를 구한뒤 합을 구함

02. 합이 m을 넘지 않는지 확인하고 이전 최대값과 비교하여 최대값 갱신

구현하기

package BackJoon.브루트포스;
import java.util.Scanner;
/**
 * https://www.acmicpc.net/problem/2798
 * @author troh
 *
 */
public class _2798_블랙잭 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m  = sc.nextInt();
        int[] cards = new int[n];
        for(int i=0; i<cards.length; i++) {
            cards[i] = sc.nextInt();
        }
        int result = getMaxCardsSum(cards, n, m);
        System.out.println(result);
    }
    
    private static int getMaxCardsSum(int[] cards, int n, int m) {
        int max = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(i == j) continue;
                for(int k=0; k<n; k++) {
                    if(k == i || k == j) continue;
                    // n개의 원소중 3개를 취합
                    int cardsSum = cards[i] + cards[j] + cards[k];
                    // 원소의 합이 m을 넘으면 무시하고
                    if(cardsSum > m) {
                        continue;
                    }
                    // 현재 최대값과 비교하여 갱신
                    max = max < cardsSum ? cardsSum : max;
                }
            }
        }
        return max;
    }
}
 

배운점

문제의 핵심은 n개의 원소중 3개를 선택할 수 있는 경우의 수를 구하는 부분이였던 것 같습니다.