[파이썬, Java] 2798. 블랙잭

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

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

입력

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

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

출력

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

예제 입력 1 

5 21

5 6 7 8 9

예제 출력 1 

21

예제 입력 2 

10 500

93 181 245 214 315 36 185 138 216 295

예제 출력 2 

497

 

 

🎨 나의 풀이

import sys

input = sys.stdin.readline
N, M = map(int, input().split())  # 카드의 개수
card = list(map(int, input().split()))
ans = 0
visited = [0] * N


def solution(depth, total):
    global ans
    if depth == 3:
        if total > M:
            return
        ans = max(ans, total)
        return

    for i in range(N):
        if not visited[i]:
            visited[i] = 1
            solution(depth + 1, total + card[i])
            visited[i] = 0


solution(0, 0)
print(ans)

백트래킹 풀이

카드를 3장 고르면 return 하고, 또 다른 카드 조합을 만드는 식으로 이 과정이 반복된다.

 

 

import sys
input=sys.stdin.readline
N, M=map(int, input().split())          # 카드의 개수
card=list(map(int, input().split()))
ans=0

def solution(depth, total, idx) :
    global ans
    if depth == 3 :
        if total > M :
            return
        ans=max(ans, total)
        return

    for i in range(N) :
        if idx & (1<<i) == 0 :
            solution(depth+1, total+card[i], idx | (1<<i))

solution(0, 0, 0)
print(ans)

비트마스크 풀이

visited 리스트를 쓰는 대신에 idx에 방문한 인덱스를 추가했다.

실행 속도는 위의 백트래킹 풀이가 더 빨랐다.

 

 

import java.io.*;
import java.util.*;

class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        Integer[] card = new Integer[N];
        int sum=0;
        int ans=0;
        st=new StringTokenizer(br.readLine());

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

        Arrays.sort(card, Collections.reverseOrder());

        for(int i=0; i<N-2; i++){
            for(int j=i+1; j<N-1; j++){
                for(int x=j+1; x<N; x++){
                    sum=card[i]+card[j]+card[x];
                    if(sum > ans && sum <= M){
                        ans=sum;
                    }
                }
            }
        }
        System.out.println(ans);
    }
    }

다른 사람의 파이썬 풀이를 자바로 구현해보았다.

내림차순 정렬할 때 Integer 타입으로 배열을 생성한 후 Collections.reverseOrder를 써야겠다.

 

 

🦔 다른 사람 풀이

# https://duwjdtn11.tistory.com/297
from itertools import combinations

card_num, target_num=map(int, input().split())
card_list=list(map(int, input().split()))
biggest_sum=0

for cards in combinations(card_list, 3) :
    temp_sum=sum(cards)
    if biggest_sum < temp_sum <= target_num :
        biggest_sum=temp_sum
print(biggest_sum)

combinations 함수로 카드 3장으로 이루어진 조합을 만든다.

temp_sum이 정답 biggest_sum 보다 크고 target_num 이하면 정답 biggest_sum을 갱신한다.

 

 

def P(n,m,c):
	t=set()
	for i in range(n-2):
		for o in range(i+1,n-1):
			for p in range(o+1,n):
				s=c[i]+c[o]+c[p]
				if s<=m:
					t.add(s)
					break

	return max([*t])
print(P(*map(int,input().split()),list(sorted(map(int,input().split()))[::-1])))

for문을 많이 쓰면 시간복잡도가 안 좋아지는 줄 알았는데 꼭 그런 것은 아닌 것 같다.

이 풀이가 내 풀이보다 훨씬 빠르다..

N^3보다 시간이 적게 걸린다.

테케 1번

set을 써서 중복을 제거한다.

return max(t)를 해도 되는데 왜 굳이 *(unpacking)을 쓴거지??

빠르게 답을 찾기 위해서 내림차순 정렬한 리스트를 함수의 파라미터로 줬다.

 

 

import java.io.*;
import java.util.*;
import java.math.*;

class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        String[] line=br.readLine().split(" ");
        int N=Integer.parseInt(line[0]);
        int M=Integer.parseInt(line[1]);
        int[] input=new int[N];
        line=br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            input[i] = Integer.parseInt(line[i]);
        }

        Arrays.sort(input);
        int result=0;
        for(int i=0; i<N; i++){
            int j=i+1;
            int k=N-1;
            while(j < k){
                int sum=input[i]+input[j]+input[k];
                if(sum <= M && M-sum < M-result){
                    result=sum;
                }
                int value1=input[i]+input[j]+input[k-1];
                int value2=input[i]+input[j+1]+input[k];
                if(value1 > M || value2 > M){
                    k--;
                }else{
                    if(M-value1 < M-value2){
                        k--;
                    }else{
                        j++;
                    }
                }
            }
        }
        bw.write(result+"\n");
        bw.flush();

    }
    }

투포인터 사용

오름차순 정렬 후 반복문을 돌렸다.

value1과 value2가 숫자 M보다 커지면 k를 1 줄인다.(오름차순 정렬되어 있기 때문에 다음 반복 때는 숫자가 더 작아짐)

 

 

import java.io.*;
import java.util.*;

class Main {

    static int max=Integer.MIN_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());

        int N=Integer.parseInt(st.nextToken());
        int M=Integer.parseInt(st.nextToken());

        int[] arr=new int[N];
        st=new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            arr[i]=Integer.parseInt(st.nextToken());
        }

        go(0, 0, arr, M, 0);

        System.out.println(max);
    }

    public static void go(int idx, int sum, int[] arr, int M, int count){
        if(count == 3){
            if(max <= M){
                max=Math.max(sum, max);
            }
            return;
        }

        for(int i=idx; i<arr.length; i++){
            if(sum+arr[i] > M) continue;
            go(i+1, sum+arr[i], arr, M, count+1);
        }
    }
    }

dfs로 구현

 

 

 

문제 출처 👉 백준