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

알고리즘 종류 브루트포스

🔗 문제 출처 https://www.acmicpc.net/problem/2798

📎

이 문제에서 사용되는 알고리즘의 종류는 브루트포스이다. 모든 경우의 수를 순회하는 알고리즘이기 때문에 살짝은 무식해보이지만 세 개의 중첩 for문을 통해 문제를 해결하였다. for문만 무난히 활용할 줄 안다면 쉽게 풀 수 있을 것이다.

📎 코드

python

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

arr = []
for i in range(0,n-2):
  for k in range(i+1,n-1):
    for j in range(k+1,n):
      num = li[i]+li[k]+li[j]
      if num <= m:
        arr.append(num)

arr.sort(reverse = True)
print(arr[0])

📎

주어진 입력들 중 세 개의 수를 골라 m보다 같거나 가장 근접한 작은 값을 구하면 된다.

여기서 세 개의 수는 중첩되면 안되기 때문에 순열로 문제를 해결한다. 예를 들어 10개의 주어진 입력 값이 있다고 가정하자. 10개 중 하나를 뽑으면, 그 하나를 제외한 9개의 숫자들 중에서 하나를 다시 뽑는다. 이런 식으로 for문의 range를 하나씩 줄여가며 세 개의 공을 뽑는 것이 관건이다. for문을 돌릴 때 out of index range를 주의하자.

뽑은 세 개의 수의 합을 num이라고 할 때, num이 m을 초과하면 continue하고 m 이하라면 배열 arr에 append한다.

for문을 빠져나오고 m보다 같거나 작은 수들이 append되어 있는 arr를 거꾸로 sort한다. 이렇게 되면 m과 가장 가까운 숫자가 배열 arr의 인덱스 0에 위치할 것이다. 그러고 나서 arr[0]를 출력하면 된다.

for문이 자주 사용되고 쉬워보여도, 이렇게 여러 번 중첩되어 사용될 때는 인덱스 오류가 나거나 헷갈릴 때가 있다. 반복문을 실수 없이 쓸 수 있도록 많이 연습해야겠다.