BJ 2798 블랙잭

문제가 궁금하다면?

내가 시도한 방법

1. N장의 카드를 배열로 입력받고,
2. 재귀를 사용해서 조합을 구한다.
3. 다만, 그 과정에서 카드의 합이 M을 넘으면 해당 조합의 탐색은 멈춘다.(가지치기)
   (가지치기를 좀 더 효율적을 하기 위해 카드 배열을 내림차순으로 정렬)

def nCr(r, n, start, total):
    global ans
    if total > M:
        return

    if not r:
        if ans < total:
            ans = total
        return

    for i in range(start, n):
        if not used[i]:
            used[i] = 1
            nCr(r-1, n, i+1, total + cards[i])
            used[i] = 0


# N = 카드의 개수 / M = 목표 숫자(카드 3장의 합은 M을 넘지 않고 가장 가깝게)
N, M = map(int, input().split())
cards = sorted(list(map(int, input().split())), reverse=True)
ans = 0
used = [0] * N
nCr(3, N, 0, 0)
print(ans)

다른 사람 풀이를 보고 든 생각

💡 조합을 구할 때는 for와 재귀가 가능하다는 점은 알고 있었는데,
그동안 문제를 풀때는 항상 재귀만 사용해서 당연히 재귀로 접근했던 부분이 있었다.
하지만, 해당 문제는 고정적인 r값을 가지기 때문에 충분히 for문으로도 가능하다. 이번을 기회로 한번 더 연습해보고, 좀 더 습관처럼 문제를 푸는 것도 좋지만 어떤 게 더 효율적일지 어떤 선택지가 있는지 다양하게 접근해보려는 노력을 해야할 것 같다.

# for를 이용해서 전체 조합 다 구해보기
N, M = map(int, input().split())
cards =list(map(int, input().split()))
ans = 0

for i in range(0, N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            total = cards[i] + cards[j] + cards[k]
            if ans < total <= M:
                ans = total

print(ans)