2798번 블랙잭

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

문제

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

풀이

부르트포스 알고리즘을 활용하는 문제로써 무작정 대입하여 해결하면 된다.

1. n과 m을 입력받고 n 크기의 배열을 생성한다.
2. 배열에 n 개의 값을 입력받는다.
3. 3중 for문을 사용하여 모든 경우의 수를 더해본다
   1. 3개의 값을 입력받기 때문에 1번째 for문은 n - 2 만큼 반복한다
   2. 2번재 for문은 i + 1 부터 n 까지 만큼 반복한다
   3. 3번재 for문은 j+ 1 부터 n 까지 만큼 반복한다
   4. 3개의 값을 모두 더한 다음 m과 같다면 해당 값을 반환
   5. 더한 값이 m보다  작다면 현재 저장된 값과 비교하여 더 큰값을 저장하고 반복
   6. 반복이 끝나면 저장된 값을 반환
4. 결과를 출력

아래는 이를 구현한 코드이다.

중간에  값을 반환하기 위해 연산하는 부분은 메서드로 분리하여 작성하였다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();


        int[] arr = new int[n];

        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }

        System.out.println(sum(arr, m));
    }

    public static int sum(int[] arr, int m){
        int sum, result = 0;

        for(int i = 0; i < arr.length-2; i++){
            for(int j = i+1; j < arr.length; j++){
                for(int k = j+1; k < arr.length; k++){
                    sum = arr[i] + arr[j] + arr[k];
                    if (sum == m){
                        return sum;
                    }else if (sum <= m){
                        result = Math.max(result, sum);
                    }
                }
            }
        }
        return result;
    }
}