[브루트 포스 / Python] BOJ 2798 - 블랙잭

www.acmicpc.net/problem/2798

2798번: 블랙잭

입력

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

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

출력

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

---

해결 방법

모든 경우를 탐색하는 것이 브루트 포스의 방법이다.

주어진 카드의 모든 경우의 수를 더해서 M을 넘지 않는 가장 큰 수를 출력한다.

해결 과정

사실 몇달 전에 풀어봤던 문제였다. 이번에 블로그를 운영하게 되면서 브루트 포스부터 다시 한번 풀어봤다.

3개의 반복문을 이용하여 해결하려고 했다.

 

def main():
    n, m = map(int, input().split())
    
    card = list(map(int, input().split()))
    
    sum_list = []
    
    for i in range(n):
        for j in range(i, n):
            for k in range(j, n):
                result = card[i] + card[j] + card[k]
                if result < m:
                    sum_list.append(result)
                    
    print(max(sum_list))
    
if __name__ == "__main__":
    main()

 

우선 처음 시도했던 코드

3개의 카드를 더한 값이 m보다 작으면 sum_list에 저장하고 최종적으로 이 값 중 제일 큰 값을 출력하게 만들었다.

 

하지만

 

 

ㅋㅋㅋㅋ... 정말 단순한 문제였는데 "틀렸습니다"가 나와서 살짝 당황했다.

곰곰히 생각해봤더니 반복문의 범위에 문제가 있었다.

내가 짠 코드는 중복 선택이 가능한 카드 선택.

하지만 문제에서 요구하는 건 중복 선택이 불가능한 카드 선택.

따라서 코드의 범위를 다시 바로 잡아 주었다.

추가적으로 불필요하게 리스트를 탐색하는 과정을 넣은 것 같아서 삭제해줬다.

 

def main():
    n, m = map(int, input().split())
    
    card = list(map(int, input().split()))
    
    result = 0
    
    for i in range(n-2):
        for j in range(i+1, n-1):
            for k in range(j+1, n):
                three = card[i] + card[j] + card[k]
                if result < three and three < m:
                    result = three
                    
    print(result)
    
if __name__ == "__main__":
    main()

 

기존의 방법인 m보다 작으면 리스트에 넣고 최종적으로 탐색하는 방법이 아닌 그때 그때 최댓값으로 갱신해주도록 코드를 변경했다.

 

 

하지만...?

또 틀렸습니다였다...ㅋㅋㅋㅋ

이번에도 범위의 문제였다. 최댓값을 갱신해주는 과정에서 카드 3개의 합이 m보다 작을 때로 구현한 것이었다.

이 부분을 수정하였고

 

 

 

통과할 수 있었다.

 

최종 코드는

 

def main():
    n, m = map(int, input().split())
    
    card = list(map(int, input().split()))
    
    result = 0
    
    for i in range(n-2):
        for j in range(i+1, n-1):
            for k in range(j+1, n):
                three = card[i] + card[j] + card[k]
                if result < three and three <= m:
                    result = three
                    
    print(result)
    
if __name__ == "__main__":
    main()

 

+ 추가로 몇달 전에 풀었던 코드를 살펴봤다.

 

from itertools import combinations
import sys
new_list = []

card, max_sum = map(int, input().split())
card_list = list(map(int, sys.stdin.readline().split()))
combi = combinations(card_list,3)
combi = list(combi)
check = 0

for i in range(len(combi)):
    if sum(combi[i]) == max_sum:
        print(sum(combi[i]))
        check += 1
        break
    else:
        if sum(combi[i]) < max_sum:
            new_list.append(sum(combi[i]))
if check != 1:
    print(max(new_list))

 

내장함수를 사용했었다.

combinations를 사용하여 모든 조합의 경우의 수를 찾아내고 이를 리스트화 하였다. (리스트에는 각 조합이 담겨있다.)

이후 반복문을 통하여 리스트의 모든 조합의 합을 계산하고 이 값이 m과 같으면 반복문을 종료한다.

그렇지 않은 경우에는 새로운 리스트에 조합의 합을 넣어줬다. (진짜 불필요한 과정이 너무 많았다...)

이후 새로운 리스트에서 최댓값을 출력... ㅋㅋㅋㅋ

이번에 짠 코드랑 시간에 2배 넘게 차이가 나는데는 이유가 있었다.

 

지난 코드를 보고 문득 생각난 것이 있는데

이번에 짠 코드의 메모리 사용량을 더 줄일 수 있겠구나란 생각이 들었다.

 

1. sys.stdin.readline()을 사용하고

2. 최댓값으로 갱신해주는 과정에서 result == m이 되면 반복문을 탈출하도록 구현하는 것이다. 그 이후의 탐색은 의미가 없기 때문이다.

 

아무튼 여기까지.