[Python] 백준 2798 문제 풀이, 브루트 포스

2798 문제 #블랙잭)

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

2798번: 블랙잭

 

 

브루트 포스 분야에 있는 문제다.

브루트 포스란 완전 탐색 알고리즘이라고도 불린다.

 

즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.

이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다.

 

   - 일반적 방법으로 문제를 해결하기 위해서는 모든 자료를 탐색해야 하기 때문에 특정한 구조를 전체적으로 탐색할 수

     있는 방법을 필요로 한다.

   - 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다.

 

 

 

 

결국... 다 넣어보면서 가능한지 구하란 것이다... 당연히 다중 for문이 쓰일 것

문제를 자세히 보자

 

 

요약해보자면

N장의 카드 중 3장의 카드를 골라서 카드의 합이 M을 넘지 않으며 M가 최대한 가깝도록 만들어야 된다는 것이다.

 

 

 

 

 

아래는 문제의 이해를 돕기 위한 입력값과 출력값이다.

예제를 보면 N장의 숫자를 넣겠다는 N과 최대 숫자인 M을 입력받은 후

N개의 수를 사용자에게 입력하게 한다.

 

먼저 입력값을 받는 단계부터 코드를 짜보자.

 

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

 

 

위의 코드가 이해가 안 된다면 아래 링크 참조!

https://mikrkosmos97.tistory.com/123

백준 문제 풀이 #1000 (split(), input() 함수 활용)

 

 

그리고 5개의 정수 list를 만들어야 되므로

 

nList = list(map(int, input().split()))

 

입력은 다 받았다. 이제 브루트 포스만 해주면 됨 굿

 

 

nList에 있는 숫자를 모두 돌려보며 세 개의 합을 구해야 된다. 그러면 for문을 통해 한 값을 가져오고 for문을 통해 한 값을 가져오고 또 for문을 통해 한 값을 가져와서 그 세 개의 값들의 합을 구하면 되겠다.

! 이때 세 값은 모두 달라야 된다.(세 장의 카드 값은 다 다를 것이므로... 중복 숫자도 제거해 줘야 됨) !

 

위의 조건들에 따라 코드를 짜보자

 

먼저 3중 for문이 필요할 것이다,

 

for i in nList:
    for j in nList:
        for j in nList:

 

이때 중복이 안 된다는 조건이 필요하므로

 

for i in nList:
    for j in nList:
        for k in nList:
            if (i==j)|(j==k)|(k==i):
                continue

 

사실 continue인지 break인지 헷갈렸다.

그래서 찾아온 pass, continue, break의 차이점 ㅎㅎ

 

1.     pass : 실행할 코드가 없는 것으로 다음 행동을 계속해서 진행합니다.

2.     continue : 바로 다음 순번의 loop를 수행합니다.

3.     break : 반복문을 멈추고 loop 밖으로 나가도록합니다.

 

위 상황에선 답을 찾아서 반복문을 멈추는 게 아니라 다른 값들도 모두 대입한 후 최종 값을 찾아야 되기 때문에

continue를 사용하여 다음 순번의 loop를 수행해야 된다.

 

 

위의 조건을 모두 만족한 값들 중에서 M보단 작(거나 같)은 제일 큰 세 합을 구해야 된다.

일단 합의 변수명을 뭐로 할까 하다가... hap으로 정했다 ㅎㅎ

 

또한 조건에 맞는 값을 담아주기 위해 max 변수를 선언했다(맨 위에) 기준이 되어야 하므로 초기값은 0으로 설정

그렇다면 최종값이 되려면 max보단 크고... M보단 작아야 될 것이다.

 

위의 기준을 모두 만족시키기 위한 코드는

 

	hap = i+j+k 
        if (max < hap) & (hap <= M):
            max = hap
print(max)

 

그냥 출력까지 해버렸다 굿

 

 

 

그래서 최종 코드는

N, M = map(int, input().split())
nList = list(map(int, input().split()))
max = 0

for i in nList:
    for j in nList:
        for k in nList:
            if (i==j)|(j==k)|(k==i):
                continue	
        
            hap = i+j+k 
            if (max < hap & hap <= M):
            max = hap
print(max)