1학기 4주차 알고리즘 과제 (2798번 : 블랙잭)

2798번: 블랙잭 (acmicpc.net)

 

문제

 

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 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. 카드 개수 N을 입력받는다.

2. M을 입력받는다.

3. N장 중 3장을 골라 합이 M을 넘지 않으면서 M과 근접하도록 합을 구한다.

 

 

카드개수 5 입력 후 M 을 21로 입력받은 후 , 5,6,7,8,9 이렇게 5장의 카드 중에서 3개의 카드를 골라 21과 근접하면서 21을 넘지 않도록 5+6+7= 18 , 5+6+8= 19, 5+6+9=20, 6+7+8= 21, 6+7+9= 22 (숫자를 넘어서 탈락)

이런식으로 합을 구하면 될 것 같다.

 

그러면 이제 N= int(input())을 통해 입력 받고, M=int(input())을 통해 입력받는데, 구분을 해주기위해 split을 써줄 것이다.

그리고 map을 통해서 다들 여러개 입력받을 때 쓰길래 나도 써보려고 한다.

 

입력받은 숫자들을 저장하는 리스트를 만들고, for문을 통해서 더한 수들이 M보다 큰지 비교하는 if 문을 사용할 것이다.

 

 

 

파이썬 여러 개 입력받기 python inpu.. : 네이버블로그 (naver.com)

파이썬 여러 개 입력받기 python input map

 

📌  코드 및 설명

 

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

d = list(map(int, input().split())) 
result = 0
Max = 0

for i in range(N-2): 
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if d[i]+d[j]+d[k] > M: 
                continue
            else:
                result = d[i]+d[j]+d[k]
                if Max <= result: 
                    Max = result

print(Max)

 

 

약간의 도움을 받아서 코드를 완성😂

 

일단은 N,M을 입력받고, list를 정의해서 입력 받도록한다.

result 값과 Max를 초기화한 후 for반복문을 중첩으로 입력받아서 총 3개의 값이 더해졌을 때 M보다 큰지 비교하는 구간을 갖고 크다면 continue를 통해 건너뛰도록하고 만약에 작거나 같다면 result를 Max에 대입하도록 한다음 print를 통해 출력하도록 한다.

 

 

 

 

 

다른 풀이도 있길래 참고하기 위해 가져와봤다.

 

느낀점 : 하나의 알고리즘 문제에는 너무 다양한 풀이법이 존재한다. 

지금은 한 방법을 생각해내는 것도 쉽지않지만, 앞으로는 더 효율적으로 코드가 짜여있는 다양한 방법들을 찾아보고 고민해보는 것도 좋은 공부가 될 것 같다.

 

이번주 알고리즘 과제 끝!

 

✔itertools 라이브러리의 순열, 조합으로 푸는 방법

 

순열 ➡  순서를 고려하여 뽑는 경우의 수

• permutations(iterable객체, r개)
• iterable 객체 : 반복문, 리스트 등 반복 가능한 객체
• r개 : 해당 객체에서 중복을 허용하지 않고 뽑을 개수(생략 가능)
• 순서대로 뽑는다.

import itertools

lst = ['A', 'B', 'C']
print(list(map(''.join, itertools.permutations(lst))))
print(list(map(''.join, itertools.permutations(lst, 2))))

['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']
['AB', 'AC', 'BA', 'BC', 'CA', 'CB']

 

 

조합 ➡ 순서를 생각하지 않고 뽑는 경우의 수

• combinations(iterable객체, r개)
• iterable 객체 : 반복문, 리스트 등 반복 가능한 객체
• r개 : 해당 객체에서 중복을 허용하지 않고 뽑을 개수(생략 안됨)
• 뽑는 순서를 고려하지 않는다. -> (AB와 BA를 같은 것으로 본다.)

 

 

✔combinations를 이용한 풀이

from itertools import combinations

N, M = map(int, input().split())
lst = list(map(int, input().split()))
nlst = []

for three in combinations(lst, 3):
    if sum(three) > M:
        continue
    else:
        nlst.append(sum(three))
print(max(nlst))

 

 

📌  참고자료

 

[python] 백준 2798 : 블랙잭 — lazarus0320 (tistory.com)

[python] 백준 2798 : 블랙잭

[백준] 2798번 블랙잭 (Python) (tistory.com)

[백준] 2798번 블랙잭 (Python)