[백준 알고리즘]2798번 블랙잭 문제 브루트 포스 알고리즘 풀이

 

 

 

 

 

 

 

문제 분석

이 문제에서 카드는 N장까지 주어지며 이 중 3장의 카드를 뽑아야 한다. 서로 다른 카드를 3장 선택할 경우 나올 수 있는 모든 경우의 수는 N*(N-1)*(N-2) = 약 N^3가지가 된다. 만약 카드가 최대 100장이라하더라도 시간 복잡도가 O(N^3)인 알고리즘을 사용했을때 연산 횟수는 100^3 = 1,000,000번밖에 되지 않는다. 따라서 이 문제는 3중 for문을 사용해서 알고리즘을 구현해도 통과할 수 있는 문제이다.

 

 

 

중복 제거

앞서 N장의 카드 중 서로 다른 카드를 3장 뽑아서 만들 수 있는 경우의 수는 N*(N-1)*(N-2)가지라고 했다. 하지만 이것은 중복되는 경우의 수를 모두 허용한다. 예를 들어 1,2,3이 적힌 3장의 카드를 뽑는다고 생각해보자. 이때 나올 수 있는 경우의 수는 다음과 같다.

 

(1,2,3), (2,1,3), (2,3,1), (1,3,2), (3,1,2), (3,2,1)

 

위와 같은 경우 각 카드를 뽑은 순서가 서로 다르지만 결과적으로  모두 1,2,3이라는 동일한 카드를 뽑은 것이다. 즉 중복된 결과를 허용한다. 이러한 중복되는 경우의 수를 제거하려면 다음 내부 for문에 진입 시 새로 선택한 카드가 이전에 선택한 카드와 같은지 확인하는 작업을 추가해야 한다.

 

 

 

코드 구현

import java.util.Scanner;

public class Blackjack {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner input = new Scanner(System.in);
		String[] firstLine = input.nextLine().split("\\s");
		int N = Integer.parseInt(firstLine[0]);//카드 장 수
		int M = Integer.parseInt(firstLine[1]);//외친 숫자
		int max = 0;// 카드 3장으로 조합된 최댓값
        
		//카드 리스트 초기화
		String[] secondLine = input.nextLine().split("\\s");
		int[] cards = new int[N];
		
		for(int i=0; i< cards.length; i++) {
			cards[i] = Integer.parseInt(secondLine[i]);
		}
		
		for(int i = 0; i < cards.length; i++) {//첫번째 카드 선택
			for(int j = 0; j < cards.length; j++) {//두번째 카드 선택
				if(i==j) {//중복 선택 방지
					continue;
				}
				for(int k = 0; k < cards.length; k++) {//세번째 카드 선택
					if(i==k||j==k) {//중복 선택 방지
						continue;
					}
					//새로 조합한 값이 M이하이고 이전에 조합된 최댓값 이상이면
					if(cards[i]+cards[j]+cards[k] <= M && max <= cards[i]+cards[j]+cards[k]) {
						max = cards[i]+cards[j]+cards[k];//새로운 조합값을 최댓값으로 설정
					}
				}
			}	
		}
		System.out.println(max);
		input.close();
	}

}