[Baekjoon | 백준] 2798번 블랙잭 (파이썬/브루트포스, itertools;순열, 조합)

문제

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

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

알고리즘 분류

• 브루트포스 알고리즘

 

문제 풀이

for문과 문자열만으로 푼 문제였으나 여러 장의 카드 중에서 3장을 뽑는 행위는 순열과도 같은 것이기 때문에 이 문제를 딱 보았을 때 순열을 사용하고 싶었으나 사용 방법을 몰라 for문으로 특정 패턴을 찾아서 풀었다.

 

어떤 것이 더 좋은 풀이일지는 모르겠으나 내가 푼 풀이와 순열으로 푼 풀이를 둘 다 올려 비교해 보겠다.

 

 

1번 풀이: 성공

패턴을 찾아 푼 내 풀이 방법이다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
cards = list(map(int, input().split()))

cards.sort()

answer = 0

for i in range(len(cards)):
    for j in range(i+1, len(cards)):
        for k in range(j+1, len(cards)):
            tmp = cards[i] + cards[j] + cards[k]
            if tmp <= M:
                answer = max(tmp, answer)
                

print(answer)

위 코드를 보면 알 수 있겠지만 고민의 흔적이 보일 것이다. 일단 케이스는 카드를 10장 뽑는 경우라고 생각하고 패턴을 찾아보았다.

• 먼저 가장 바깥 for문에서는 카드 3 장을 뽑을 때 가장 왼쪽에 있는 경우이기 때문에 8, 9번 인덱스까지 포함해 버리면 이 index가 가장 왼쪽에 있으면서 카드 3장을 뽑는 것이 불가능하다.
• 2 번째 for문은 중간에 위치한 카드이므로 현재 왼쪽에 위치한 카드의 바로 다음부터 시작하여 8번 인덱스 까지 진행하였다.(이유는 위와 같음)
• 가장 안쪽 for문은 마지막에 위치한 카드로 중간에 위치한 카드의 바로 다음부터 시작하여 가장 마지막 인덱스까지 접근하면 모든 경우를 다룰 수 있게 되는 것이다.

이제 각 경우의 i, j ,k 의 값들을 모두 더하였을 때 M의 크기보다 작으면서 max 보다 크게 되면 max에 계속해서 업데이트 되는 식으로 코드를 짰다.

 

 

순열을 사용한 다른 풀이

from itertools import combinations

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

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

print(biggest_sum)

위처럼 파이썬에서 제공하는 순열 조합 라이브러리 itertools 모듈의 combinations라는 함수를 사용하면 된다.

 

추가적으로 itertools에 대한 설명을 진행하겠다.

combinations(iterable, r) : iterable 에서 원소 개수가 r개인 조합 뽑기

 

from itertools import combinations

l = [1,2,3]

for i in combinations(l,2):
    print(i)

'''
출력 결과:
(1, 2)
(1, 3)
(2, 3)
'''

파이썬 공식문서에 따르면 입력 iterable의 순서에 따라 사전식 순서로 release 된다. 따라서 입력 iterable이 정렬되어있으면, 조합 튜플이 정렬된 순서로 생성된다.

 

조합이란 서로 다른 n개에서 r개를 선택할 때 순서를 고려하지 않고 선택한 경우의 수를 나열하는 방법이다. 보통 Combination의 첫 글자 C를 따서 nCr로 표현하며 계산식은 아래와 같이 쓸 수 있다.

• nCr = n x (n-1) x (n-2) x .... x (n-r+1) / r x (r-1) x (r-2) x .... x 2 x 1
• nCr = n! / r!(n-r)!

가령 알파벳이 써져 있는 카드 4개가 있다고 해보자. 각 카드에는 A, B, C, D가 써져 있는데 공식에 따르면 4C2=4x3/2x1=6 혹은 4C2 = 4! / 2!(4-2)! = 4 x 3 x 2 x 1 / 2 x 1 x 2 x 1 = 6 이므로 총 6개의 경우의 수가 나오게 된다.

 

AB, AC, AD

BA, BC, BD

CA, CB, CD

DA, DB, DC

 

AB와 BA는 같은 경우의 수이기 때문에 

 

 

combinations_with_replacement(iterable,r) : iterable에서 원소 개수가 r개인 중복 조합 뽑기

from itertools import combinations_with_replacement

l = ['A', 'B', 'C']

for i in combinations_with_replacement(l,2):
    print(i)

'''
출력결과:
('A', 'A')
('A', 'B')
('A', 'C')
('B', 'B')
('B', 'C')
('C', 'C')
'''

 

 

 

 

permutations(iterable,r=None) : iterable에서 원소 개수가 r개인 순열 뽑기

from itertools import permutations

l = ['A', 'B', 'C']

for i in permutations(l): #r을 지정하지 않거나 r=None으로 하면 최대 길이의 순열이 리턴된다!
    print(i)

'''
출력결과:
('A', 'B', 'C')
('A', 'C', 'B')
('B', 'A', 'C')
('B', 'C', 'A')
('C', 'A', 'B')
('C', 'B', 'A')
'''

순열이란 서로 다른 n개에서 r개를 선택할 때 순서를 고려하여 선택한 경우의 수를 나열하는 방법이다. 보통 Permutation의 첫 글자 P를 따서 nPr로 표현하며 계산식은 아래와 같이 쓸 수 있다. ( 0 ≤ r ≤ n )

• nPr = n x (n-1) x (n-2) x (n-3) x .... x (n-r+1)  ※ n부터 (n-r+1)까지 곱해지는 수는 총 r개
• nPr = n! / (n-r)!

가령 알파벳이 써져 있는 카드 4개가 있다고 해보자. 각 카드에는 A, B, C, D가 써져 있는데 이 중에서 순서를 고려하여 2장을 뽑고 싶다고 하자. 공식에 따르면 4P2=4x3 = 12 혹은 4P2 = 4! / (4-2)! = 4x3x2x1 / 2x1 = 4x3=12 이므로 총 12개의 경우의 수가 나올 것이라 생각 할 수 있다. 실제로 2장을 뽑은 결과를 나열하면 다음과 같다.

 

AB, AC, AD

BA, BC, BD

CA, CB, CD

DA, DB, DC

 

여기서 순서를 고려한다는 것은, AB와 BA를 서로 다른 것이라고 여기는 것을 의미한다.

 

product(*iterables, repeat=1) : 여러 iterable의 데카르트곱 리턴

product는 다른 함수와 달리 인자로 여러 iterable을 넣어줄 수 있고 그 친구들간의 모든 짝을 지어서 리턴한다.

from itertools import product

l1 = ['A', 'B']
l2 = ['1', '2']

for i in product(l1,l2,repeat=1): #l1과 l2의 모든 쌍을 지어 리턴한다
    print(i)

'''
출력결과:
('A', '1')
('A', '2')
('B', '1')
('B', '2')
'''

for i in product(l1,repeat=3): #product(l1,l1,l1,repeat=1)과 동일한 출력
    print(i)

'''
출력결과:
('A', 'A', 'A')
('A', 'A', 'B')
('A', 'B', 'A')
('A', 'B', 'B')
('B', 'A', 'A')
('B', 'A', 'B')
('B', 'B', 'A')
('B', 'B', 'B')
'''

 

주의할 점

단 이 조합이나 순열을 사용할 때 주의해야 할 점은 n의 크기가 커지면 커질 수록 굉장히 많은 경우의 수가 생기기 때문에 코딩 테스트 문제를 조합이나 순열을 사용하는 경우 n의 크기를 반드시 고려해야 한다.

 

그래서 보통 완전탐색을 할 수 있는 n의 크기라면 조합이나 순열을 잘 활용하면 코드가 굉장히 간결해 질 수 있다.

 

순열 같은 경우 모든 경우의 수를 다 보기 때문에 시간 복잡도가 O(n!)라는 시간이 걸리게 된다.

보통 1초에 1억 번이라는 연산을 기준으로 잡기 때문에 12! 이상이 되면 시간 초과가 뜨게 된다.

위 문제 같은 경우 문제의 사이즈가 8이므로 8!=40320이라는 적은 경우의 수이므로 순열로 풀게 되어도 문제가 되지 않는다.

앞으로 순열을 이용할 경우 문제의 사이즈를 유의해서 보도록 하자.