[백준]블랙잭_2798

문제설명

'카지no(노)'라는 단어를 본문에 쓰면 자동으로 비공개가 전환된다. velog의 검열은 이런 방식으로 하나보다.따라서 문제를 사진으로 첨부했다.

입력

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

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

출력

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

예제 입력 및 출력

문제 분석 -> 사고의 방식

• 첫째 줄에서 카드의 개수 및 3합 최대의 값 저장
• 둘째 줄에서 for문을 돌려 3합이 최대보다 작으면서 최대가 될때, 또는 3합의 값이 최댓값과 같을 때로 조건을 걸고 식을 돌림(여기서 브루트포스 알고리즘이 활용됨)

브루트 포스란?

• brute:무식한 , force:힘
• 무식한 힘으로 탐색한다. -> 완전탐색
• 가능한 모든 경우의 수를 탐색하여 문제를 해결하는 알고리즘입니다.
• 대개 문제의 크기가 작고 경우의 수가 적을 때 사용합니다.
• 경우의 수가 많아질수록 계산 속도가 느려집니다.
• 최적의 결과를 보장합니다.

여기서 더 알아보고자 DFS, BFS에 대한 브루트포스와 비교하여 정리하였다.

DFS

• 그래프에서 깊이를 우선으로 탐색하는 알고리즘입니다.
• 스택(stack) 자료구조를 사용합니다.
• 그래프의 끝까지 탐색을 하며, 더 이상 갈 곳이 없으면 이전 노드로 돌아가서 탐색을 계속합니다.
• 해를 찾거나 모든 노드를 탐색할 때까지 탐색을 진행합니다.

예시: 미로 찾기 문제

BFS

• 그래프에서 너비를 우선으로 탐색하는 알고리즘입니다.
• 큐(queue) 자료구조를 사용합니다.
• 시작 노드에서 시작하여 인접한 모든 노드를 방문한 후, 다음 노드를 방문합니다.
• 최단 경로를 구하는 문제에 사용됩니다.

예시: 지도에서 두 도시 간의 최단 거리를 구하는 문제

문제 풀이

1. blackJack 함수

public class blackJack {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int count = Integer.parseInt(st.nextToken());
        int maxNum = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());

        List<Integer> card = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            card.add(Integer.parseInt(st.nextToken()));
        }

        int result = findMaxSum(card, count, maxNum);
        System.out.println(result);
    }

• blackJack 함수에서는 입력을 받아들임.
• 첫 줄에서는 카드의 개수와 최대 숫자 합을 입력받고, 두 번째 줄에서는 카드의 숫자를 입력받습니다.
• ArraryList를 이용해 카드번호를 리스트에 저장함.(순서는 상관없음)
• 이후 findMaxSum 함수를 호출하여 결과값을 출력합니다.

2. findMaxSum 함수

static int findMaxSum(List<Integer> arr, int N, int M) {
        int maxSum = 0;
        for(int i = 0; i<N-2; i++) {
            for(int j = i+1; j<N-1; j++){
                for(int k = j+1; k<N; k++){
                    int sum = arr.get(i) + arr.get(j) + arr.get(k);

                    if(sum <= M){
                        maxSum = Math.max(maxSum, sum);
                    }
                }
            }
        }
        return maxSum;
    }
}

• 여기서 3중 for문을 돌며 브루트 포스 알고리즘이 활용됨.
• sum값이 M과 같을 경우, sum값이 M보다 작은 값중 최대일 경우 두가지를 고려해

  if(sum <= M){
      maxSum = Math.max(maxSum, sum);
  }

  위와 같이 코드를 짬.

코드 분석(feat.ChatGPT)

• 이 코드는 매우 간단하고 이해하기 쉽습니다. 하지만 카드의 개수가 매우 크거나 최대 숫자 합의 범위가 매우 넓은 경우에는 시간 복잡도가 높아져서 실행 시간이 길어질 수 있습니다. 이를 개선하기 위해서는 보다 효율적인 알고리즘이 필요합니다.
• 이 코드의 시간복잡도는 $O(n^3)$

더 효율적인 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class blackJack {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int count = Integer.parseInt(st.nextToken());
        int maxNum = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());

        int[] card = new int[count];
        for (int i = 0; i < count; i++) {
            card[i] = Integer.parseInt(st.nextToken());
        }

        int result = findMaxSum(card, count, maxNum);
        System.out.println(result);
    }

    static int findMaxSum(int[] arr, int N, int M) {
        Arrays.sort(arr);  // 카드 리스트를 오름차순으로 정렬합니다.
        int maxSum = 0;
        for(int i = 0; i < N-2; i++) {
            int j = i + 1;
            int k = N - 1;
            while (j < k) {  // 두 번째 포인터와 세 번째 포인터가 만날 때까지 반복합니다.
                int sum = arr[i] + arr[j] + arr[k];
                if (sum <= M) {  // 최대 숫자 합 이하인 경우에만 최대 숫자
                maxSum = Math.max(maxSum, sum);
        if (sum < M) { // 합이 M보다 작은 경우에는 두 번째 포인터를 오른쪽으로 이동합니다.
        j++;
        } else { // 합이 M보다 큰 경우에는 세 번째 포인터를 왼쪽으로 이동합니다.
        k--;
        }
      }
	}
    return maxSum;
  }
}

• 이 문제에서는 주어진 카드 리스트에서 가능한 모든 3장 조합 중에서, 최대 숫자 합이 최대 숫자 합 이하인 경우를 찾아야 합니다. 이를 구현하기 위해서는 먼저 주어진 카드 리스트를 오름차순으로 정렬하는 것이 좋습니다. 정렬된 리스트에서는 두 개의 포인터를 사용하여 가능한 모든 3장 조합을 탐색할 수 있습니다.

• 첫 번째 포인터는 리스트의 가장 작은 인덱스부터 시작하고, 두 번째 포인터는 첫 번째 포인터 바로 다음 인덱스부터 시작합니다. 세 번째 포인터는 리스트의 마지막 인덱스부터 시작하고, 첫 번째 포인터와 두 번째 포인터가 가리키는 카드와 함께 조합을 이룹니다.

• 이후에는 세 포인터가 가리키는 카드의 합을 구하고, 최대 숫자 합 이하인 경우에는 최대 숫자 합을 업데이트합니다. 그리고 두 번째 포인터와 세 번째 포인터를 각각 한 칸씩 왼쪽으로 이동시킵니다. 이를 반복하면 모든 가능한 3장 조합을 탐색할 수 있습니다.

• 이 알고리즘의 시간 복잡도는 O(N^2)입니다. 따라서 입력으로 큰 N값이 주어져도 빠른 실행 시간을 보장할 수 있습니다.

다른 사람의 풀이(PyPy3)

from itertools import combinations
m=list(map(int, input().split()))[1]
print(max((i for i in tuple(map(sum, combinations(tuple(map(int, input().split())), 3))) if i<=m)))

이 코드는 itertools 라이브러리의 combinations 함수를 사용하여 가능한 모든 3장 조합을 구하고, 이들의 합을 계산합니다. 이후에는 주어진 제한값 m 이하인 경우에 대해서만 최댓값을 찾습니다.

코드 분석(chatGPT)

from itertools import combinations

itertools 라이브러리의 combinations 함수를 import 합니다.

m=list(map(int, input().split()))[1]

첫 번째 입력값은 사용하지 않으므로 무시하고, 두 번째 입력값인 최대값 m을 입력받습니다. 입력값을 공백을 기준으로 나누고, 리스트 내포(list comprehension)를 사용하여 정수형으로 변환합니다.

print(max((i for i in tuple(map(sum, combinations(tuple(map(int, input().split())), 3))) if i<=m)))

• input().split(): 공백을 기준으로 입력을 나누어 리스트로 만듭니다.
• map(int, input().split()): 리스트의 각 항목을 정수형으로 변환합니다.
• tuple(map(int, input().split())): 변환된 리스트를 튜플로 만듭니다.
• combinations(tuple(map(int, input().split())), 3): 튜플에서 3개의 항목으로 이루어진 가능한 모든 조합을 생성합니다.
• map(sum, combinations(...)): 조합별로 합을 계산합니다.
• (i for i in tuple(map(sum, combinations(...))) if i<=m): 계산된 합 중에서 m 이하인 값만을 포함하는 제너레이터(generator)를 생성합니다.
• max((i for i in ... if i<=m)): 생성된 제너레이터(generator) 중에서 최댓값을 출력합니다.
• 이 알고리즘의 시간 복잡도는 조합의 개수에 비례하므로, 입력 크기가 커질수록 실행 시간이 급격하게 늘어날 수 있습니다.

하지만 itertools 라이브러리의 함수를 이용하여 코드를 작성하였기 때문에, 직접 반복문을 작성한 경우보다 실행 시간이 더 빠를 가능성이 있습니다.라고 지피티가 말함. 이상.