[BAEKJOON/백준] 2798번: 블랙잭

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

max_sum = 0  # 최대 합 초기화

# 모든 카드의 조합을 탐색
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            card_sum = cards[i] + cards[j] + cards[k]  
            if card_sum <= M and card_sum > max_sum:
                max_sum = card_sum 
print(max_sum)

 

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

---

[1] 문제 풀이

 

이 문제는 N장의 카드 중에서 3장의 카드를 선택하여 그 합이 M을 넘지 않으면서 M에 최대한 가깝게 만드는 것을 요구한다.

 

 

1. 입력 형식 :

• 첫 번째 줄에는 카드의 개수 N과 M이 주어진다.
• 두 번째 줄에는 N장의 카드에 쓰여 있는 숫자가 주어진다.

 

2. 출력 형식 :

• M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

 

이 문제를 해결하기 위해 나는 다음과 같은 방법을 선택했다. :

• 모든 카드의 조합을 찾았다. 이를 위해 가능한 모든 조합을 탐색합니다.  (이 경우 시간 복잡도는 O(N^3)이 되긴 하지만... 제한이 100개의 카드까지이므로 충분히 빠르게 동작할 것이라고 생각했다.)
• 각 조합의 합을 계산하고, M을 넘지 않는 최대의 합을 찾는다.

 

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


for i in range(N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            card_sum = cards[i] + cards[j] + cards[k] 
            if card_sum <= M and card_sum > max_sum: 
                max_sum = card_sum 

print(max_sum)

 

중첩 반복문을 중심적으로 분석을 해보자면,

 

1. 첫 번째 반복문 (for i in range(N - 2):):

이 반복문은 첫 번째 카드를 선택하는 데 사용된다.

i 변수는 0부터 N-3까지 변한다. 이는 첫 번째 카드가 선택된 후에도 두 개의 카드가 남아있어야 하기 때문이다.

이 반복문을 통해 첫 번째 카드의 인덱스를 선택한다.

 

2. 두 번째 반복문 (for j in range(i + 1, N - 1):):

이 반복문은 두 번째 카드를 선택하는 데 사용된다.

j 변수는 i 다음부터 시작하여 N-2까지 변한다. 이는 첫 번째 카드 다음부터 두 번째 카드를 선택할 수 있도록 한다.

이 반복문을 통해 두 번째 카드의 인덱스를 선택한다.

 

3. 세 번째 반복문 (for k in range(j + 1, N):):

이 반복문은 세 번째 카드를 선택하는 데 사용된다.

k 변수는 j 다음부터 시작하여 N-1까지 변한다. 이는 두 번째 카드 다음부터 세 번째 카드를 선택할 수 있도록 한다.

이 반복문을 통해 세 번째 카드의 인덱스를 선택한다.

 

 

✔️ 예를 들면...

카드 숫자: 5 6 7 8 9
M: 21

 

일 때,

 

1. 첫 번째 반복문 (첫 번째 카드 선택):

첫 번째 반복문에서는 첫 번째 카드를 선택한다. 인덱스 i는 0부터 N-3까지 변한다.

이 경우에는 0부터 2까지이다. 이에 따라 첫 번째 카드는 5, 6, 7 세 개 중에서 선택된다.

첫 번째 반복문에서 선택된 카드는 다음과 같이 된다.

 

5 6 7

 

2. 두 번째 반복문 (두 번째 카드 선택):
두 번째 반복문에서는 두 번째 카드를 선택한다. 인덱스 j는 i 다음부터 시작하여 N-2까지 변한다.

이 경우에는 i가 0일 때 1부터 3까지, i가 1일 때 2부터 4까지이다. 이에 따라 두 번째 카드는 다음과 같이 선택된다:

 

i=0: 6, 7, 8

i=1: 7, 8, 9

 

3. 세 번째 반복문 (세 번째 카드 선택):

세 번째 반복문에서는 세 번째 카드를 선택한다. 인덱스 k는 j 다음부터 시작하여 N-1까지 변한다.

이 경우에는 j가 1일 때 2부터 4까지이다. 이에 따라 세 번째 카드는 다음과 같이 선택된다:

 

i=0, j=1: 7, 8, 9

 

 

 

 

 

---

[2] 느낀 점

 

구글링을 해보니 내가 사용한 방법 이외에 여러가지 방법이 존재했는데, 파이썬 라이브러리를 이용하여 푸는 방법과 같은 경우에는 ... 파이썬 내장함수에 익숙하지 않아서 사용하지 못 해 아쉽다.

이번엔 반복문을 활용하여 풀었지만, 시간복잡도가 높은 편이라 검사하는 숫자가 커지면 아주 비효율적인 코드가 될 것 같다.

1학년 당시에 코드를 짤 때는 반복문 범위 설정을 어려워했었는데, 그 부분은 좀 나아진 것 같다.