[BOJ] 2798 - 블랙잭

엄혜영·2024년 3월 23일

algorithm boj

알고리즘 챌린저까지

목록 보기

6/11

이 문제는 정말 어떻게 풀어야할지 감이 안온다.

일단 생각나는 방법은 for 문을 세번 중첩하여 사용하는건데...

답은 나오긴 하겠다만 효율적인 방법인지는 모르겠다.

지금 하고있는 부트캠프에서도 비슷한 유형의 과제를 내줬다.

Leet Code의 Two Sum 문제를 약간 변형하여 k값을 입력받아 nums 중 k개의 합이 target이 되도록 푸는 것이다.

이 문제에서도 for 문을 사용한다면 k값에 따라서 for 문의 중첩 횟수가 늘어날 것이다.

이러한 방법으로 코드를 짜는것은 그다지 효율적일 거라 생각이 들지 않는다.

따라서 해당 문제들을 풀기 위해서 푸는 방법을 먼저 공부하는 식으로 진행 해봤다.

해결 방법: itertools

이런 문제는 파이썬에서 제공하는 순열 조합 라이브러리 itertools 모듈을 사용하면 된다.

itertools는 반복되는 데이터 처리를 하는 파이썬 라이브러리이다.

itertools의 함수들을 연습할 수 있는 문제는 이 블로그에 아주 잘 정리되어 있다.

각 함수마다 한 문제씩 풀어보며 연습하는 것을 추천한다!

[참고] 순열과 조합

순열과 조합... 아주 옛날에 배워서 다 까먹었다.

아래는 나같은 사람을 위한 순열과 조합의 간단한 정리이다.

순열(permutation)
서로 다른 n개의 원소를 갖는 집합에서 r개의 원소를 중복없이 순서를 고려하여 나열하는 것.

조합(combination)
서로 다른 n개의 원소를 갖는 집합에서 r개의 원소를 중복과 순서 없이 선택하는 것.

permutations (중복 없는 순열)

iterable 객체에서 r개의 데이터를 뽑아 일렬로 나열하는 모든 경우를 제시한다.

permutations(iterable, r)

연습문제
[BOJ]10819-차이를 최대로

from itertools import permutations

n = int(input())
a = list(map(int, input().split()))
perm = list(permutations(a, n))
permMax = 0

for i in perm:
    permSum = 0
    for j in range(n-1):
        permSum += abs(i[j] - i[j+1])
    if permSum > permMax:
        permMax = permSum

print(permMax)

combinations (중복 없는 조합)

iterable 객체에서 r개의 데이터를 뽑아 순서없이 일렬로 나열하는 모든 경우를 제시한다.

combinations(iterable, r)

연습문제
[BOJ]15650-N과 M (2)

from itertools import combinations

n, m = map(int, input().split())
combs = list(combinations(range(1, n+1), m))
for i in combs:
    print(*i)

팁: 리스트 앞에 *을 붙이면 for문을 사용하지 않고도 리스트 요소를 한번에 띄어쓰기 출력이 가능하다.
조합은 자동으로 사전 순(오름차순)으로 만들어진다. 이를 명심하자!

product (중복 있는 순열)

함수 안에 제시된 모든 iterable 객체에서 1개씩 데이터를 뽑아 일렬로 나열하는 모든 경우를 제시한다.

product(iterable1, iterable2)

또는 iterable 객체에서 r개의 데이터를 중복을 포함하여 뽑아 일렬로 나열하는 모든 경우를 제시한다.

product(iterable, repeat=r)

연습문제
[BOJ]15651-N과 M (3)

from itertools import product

n, m = map(int, input().split())
nlist = list(product(range(1, n+1), repeat=m))
for i in nlist:
    print(*i)

combinations_with_replacement (중복 있는 조합)

iterable 객체에서 r개의 데이터를 중복을 포함하여 뽑아 순서없이 일렬로 나열하는 모든 경우를 제시한다.

com(iterable, r)
iterable: 반복할 리스트
r = 중복을 포함하여 r개 뽑기

연습문제
[BOJ]15652-N과 M (4)

from itertools import combinations_with_replacement as com

n, m = map(int, input().split())
nlist = list(com(range(1, n+1), m))
for i in nlist:
    print(*i)

문제 풀이

from itertools import combinations

n, m = map(int, input().split())
cards = list(map(int, input().split()))
combCards = list(combinations(cards, 3))
save = 0

for i in combCards:
    calc = sum(i)
    if calc <= m and calc > save :
        save = calc
print(save)