Kang Chang Ryong

3 분 소요

시간 제한 메모리 제한 정답 비율
1 초 128 MB 46.180%

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 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: 성공

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

'''
0 1 2 3 4 5 6 7 8 9
'''

def solution(n, m, card):
    
    max = 0
    count = 0
    for i in range(n-2): #0~7
        for j in range(i + 1, n - 1): #1~8
            for k in range(j + 1, n): #2~9
                count = card[i] + card[j] + card[k]
                if count > max and count <= m:
                    max = count
                      
    return max


n, m = map(int, input().split())

card = list(map(int, input().split()))

print(solution(n, m, card))

위 코드를 보면 알 수 있겠지만 고민의 흔적이 보일 것이다. 일단 케이스는 카드를 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이 정렬되어있으면, 조합 튜플이 정렬된 순서로 생성된다.


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')
'''


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')
'''

댓글남기기

참고