백준 2798번 JAVA 자바 블랙잭 [브루트 포스]

카드의 개수 N (3 <= N M= 100)를 입력하고 블랙잭에 해당하는 수 M (10 <= M <= 300,000)을 입력한다.

두 번째 줄에는 N 수만큼의 카드 넘버를 입력한다. 100,000 미만의 양의 정수이다.

 

그래서 M을 넘지 않고 최대한 가까운 세 수의 합을 구하는 프로그램이다.

예제 입력2에는 10장의 카드가 있는데 이 10개의 수에서 세 개씩 더하는 모든 경우의 수를 찾아서 가장 M에 가까운 수를 구하면 된다.

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N, M;
        N = sc.nextInt();    //카드 개수
        M = sc.nextInt();    //블랙잭 (넘지않고 가까워야 하는 수)
        int sum = 0;        //세 수의 합
        int tmp = 0;         //새로운 근사치가 나올때까지 이전 근사치 값
        
        int arr[] = new int[N];
        for(int i=0; i<N; i++) {
            arr[i] = sc.nextInt();    //카드에 적힌 수
        }
        
        for(int i=0; i<N; i++) {            //N만큼 반복(배열 arr을 순회)
            for(int j=i+1; j<N; j++) {        //i+1번째 위치한 arr부터 순회
                for(int k=j+1; k<N; k++) {    //j+1번째부터 arr 순회
                    sum = arr[i] + arr[j] + arr[k];    //세 수를 더한다.
                    //근사치 (tmp) 보다 크고 블랙잭보다 작거나 같으면 새로운 근사치
                    if(tmp < sum && sum <= M)        
                        tmp = sum;
                }
            }
        }
        System.out.println(tmp);    //for문을 다 돌고 가장 근접한 근사치는 tmp에 있다.
    }
}

배열 arr[]의 길이가 5라면 

세 중첩 for문을 통해 전체의 경우의 수를 탐지한다.

   (0, 1, 2) (0, 1, 3) (0, 1, 4) 

   (0, 2, 3) (0, 2, 4)

   (0, 3, 4)

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

   (1, 3, 4)

이런 식으로 3열의 증가는 19행의 k++ for문

2열의 증가는 18행의 j++ for문

1열 증가는 17행의 i++ for문이다.