오늘의 알고리즘(4월 5일)

1. 백준, 2789번, 블랙잭

 

www.acmicpc.net/problem/2798

2798번: 블랙잭

 

---

2. 생각해보자

- 규칙은 다음과 같다. 

 

• 첫번째 입력값으로 카드 개수인 N과 최대값 M이 주어진다.
• 두번째 입력값으로 카드의 숫자 N개가 주어진다. 
• 이 문제의 핵심은 N개의 카드 중 3장의 조합을 이용하여, M에 가장 가까운 최대값을 찾는 것이다.

 

- 다음과 같은 예시를 생각해보자. 

 

먼저 N과 M을 받는 코드가 필요할 것이다. 

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

 

그리고 5개의 카드 중 3개의 조합을 만들어보자. 

[567],  [568], [569], [578] , [579], [589]

[678], [679], [689]

[789] 

 

이런 방식으로 조합을 찾는 방식을 생각해보았다. 만약 이 방법을 코드로 구현한다면 어떻게 해야할까? 

첫번째와 두번째 숫자를 고정시키고 세번째 숫자를 for문을 이용해 돌리면 가능하지 않을까? 

 

---

3. 풀이 및 코드 분석

n, m = list(map(int, input().split(' ')))
# 첫번째 입력값 N과 M을 받는다.

data = list(map(int, input().split(' ')))
# 두번째 입력값인 카드 N개의 숫자를 받는다.

result = 0 # 최대값을 저장할 변수
length = len(data) # 카드의 개수를 저장할 변수 

count = 0
for i in range(0, length):
    for j in range(i + 1, length):
        for k in range(j + 1, length): # 반복문을 이용하여 조합을 찾는다. 
            sum_value = data[i] + data[j] + data[k]
            if sum_value <= m: # 찾은 조합이 M을 초과하지 않는다면 
                result = max(result, sum_value) 
                # 가장 큰 조합을 result에 저장한다. 자세한 설명은 아래에 있다.
                
print(result)

 

---

4. 주요 함수

max

- 우선 max()의 기본형을 살펴보자.

https://docs.python.org/3/library/functions.html#max

 

1) max(iterable)

매개변수는 이터러블로 정의되어 있어야 한다. 매개변수가 갖고있는 요소 중 가장 큰 요소를 반환한다. 

https://blockdmask.tistory.com/411

 

2) max(arg1, arg2, ...) 

이터러블을 매개변수로 사용하며, 여러개의 이터러블을 비교하여 가장 큰 요소를 갖는 이터러블을 반환한다. 

https://blockdmask.tistory.com/411

 

 

3) 풀이에서 max()를 사용한 방법 

풀이 코드에서는 두번째 방법의 max()함수를 사용한 것이다. 

삼중 for문에 의하여 i, j, k의 숫자가 계속 변동되고 한번 바뀔 때마다 sum_value와 result를 비교하여 둘 중에 큰 값을 result에 저장한다. 그리고는 다시 for문을 통하여 이 과정을 반복하여 가장 조합의 큰 값을 찾게 되는 것이다.