[Baekjoon] 백준 #2798번 파이썬 해답

단계별로 풀어보기 → 브루트 포스에 위치한 문제입니다.
Brute-force search

 

문제부터 보겠습니다.

 

문제

 

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

 

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

 

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

 

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

 

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

 

출력

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

 

솔루션

 

N, M = map(int, input().split())
nlist = list(map(int, input().split()))
new_list = sorted(nlist)
klist = 0

for i in range(N):
    for j in range(i+1, N):
        for p in range(j+1, N):
            if new_list[i]+new_list[j]+new_list[p] > M:
               continue
            else:
               klist = max(klist, new_list[i]+new_list[j]+new_list[p])
print(klist)

 

---

 

💦 정확히 Brute-force가 어떤 것을 뜻하는지는 몰랐는데, 확인해보니 '완전 검색 탐색'이라는 

알고리즘 용어와는 약간 다른 뜻이 나옵니다. 영어로 Brutal은 잔인한, 짐승같은 이라는 뜻도 있지만

무식함을 뜻하는 부분도 있어서 이처럼 사용된 것 같습니다.

 

🏋️‍♀️ 차근차근 요령을 피우면서 해답을 찾기 보다는 우격다짐으로 찾는다는 느낌이 강한데요?

 

브루트포스는 일종의 수를 대입하는 "노가다"라고 이해하시면 될것 같습니다.

 

우리가 일종의 번호 자물쇠를 열어야 한다고 가정해봅시다.

 

필자한테 비밀번호에 대한 단서나 추정할 만한 정보가 없다고 한다면, 

자물쇠를 열기위해 일단 단순하게 1부터 9까지 직접 돌려보는 수밖에 없을 것입니다.

 

 

그 이외의 방법으로 천의 자리숫자를 알아낸다거나, 백의 자리숫자를 알아내는 등

숫자를 특정할 수는 있겠습니다만 정보가 없을때는 무식하게 하나씩 넣어보는 것도 가능합니다.

 

🤾‍♀️이렇게 숫자를 무식하게 하나하나 넣어보는 것이 브루트포스의 골자입니다.

 

 

 

단, brute force는 이번 문제처럼 단순한 공식에서는 복잡도
(complexity)를 크게 높이지 않지만
고려해야 할 요소가 많을 경우 시간이 매우 상승하게 된다는
치명적인 약점도 갖고 있습니다.

new_list에는 숫자 카드들이 들어간다고 생각해봅시다.

 

new_list[i]+new_list[j]+new_list[p] > M:

 

이렇게 세가지 숫자 i, j, p를 합한 것이 지정한 합계 M보다 큰 경우가 되기 전까지

계속 합해서, klist에 합해주는 것을 고려해주면 되겠습니다.

 

            if new_list[i]+new_list[j]+new_list[p] > M:
               continue
            else:
               klist = max(klist, new_list[i]+new_list[j]+new_list[p])

 

klist에는 세 숫자의 합이 M보다 작은 한, i+j+p의 합계가 모이면서, 이전의 숫자보다 더 큰 값이 나오면

klist는 대체될 수 밖에 없습니다. 

 

그리고 new_list안의 세 숫자가 모두 돌아가면 끝나는 것이지요.

이를 i, j, p 의 변수를 지정해주기 위해 for문을 써줍니다.

 

for i in range(N):
    for j in range(i+1, N):
        for p in range(j+1, N):

 

klist는 이전에 지정

 

N, M = map(int, input().split())
nlist = list(map(int, input().split()))
new_list = sorted(nlist)
klist = 0

for i in range(N):
    for j in range(i+1, N):
        for p in range(j+1, N):
            if new_list[i]+new_list[j]+new_list[p] > M:
               continue
            else:
               klist = max(klist, new_list[i]+new_list[j]+new_list[p])

 

M이하인 한에서 가장 크기가 큰 klist를 반환하면 끝납니다.

 

N, M = map(int, input().split())
nlist = list(map(int, input().split()))
new_list = sorted(nlist)
klist = 0

for i in range(N):
    for j in range(i+1, N):
        for p in range(j+1, N):
            if new_list[i]+new_list[j]+new_list[p] > M:
               continue
            else:
               klist = max(klist, new_list[i]+new_list[j]+new_list[p])
print(klist)

 

2798번도 이렇게 완료