[백준 2798번]블랙잭(파이썬)

문제 설명

 

1. 처음 나의 풀이(오답)

 

# 블랙잭
import sys
input = sys.stdin.readline

# 카드의 개수 n
n, m = map(int, input().split())

# 카드에 쓰여있는 n개의 수들
nums = list(map(int, input().split()))

result_list = []

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

# 1. 모든 합의 조합을 다 구해본다.

for i in range(len(nums)):
    for j in range(i+1, len(nums)):
        for k in range(j+1, len(nums)):
            sumOfNums = nums[i] + nums[j] + nums[k]
            
            if sumOfNums > m:
                break
            else:
                result_list.append(sumOfNums)


print(max(result_list))

 

 

 

2. 정답 처리된 풀이

카드에 쓰여있는 n개의 수들을 담는 라인만 수정한 코드이다.

 

# 블랙잭
import sys
input = sys.stdin.readline

# 카드의 개수 n
n, m = map(int, input().split())

# 카드에 쓰여있는 n개의 수들
nums = sorted(list(map(int, input().split())))

result_list = []

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

for i in range(len(nums)):
    for j in range(i+1, len(nums)):
        for k in range(j+1, len(nums)):
            sumOfNums = nums[i] + nums[j] + nums[k]
            
            if sumOfNums > m:
                break
            else:
                result_list.append(sumOfNums)

print(max(result_list))

 

3. 왜 nums를 sorted 하지 않으면 오답이 나오는가?

 

나는 세 수의 합이 m을 넘지 않는 경우, 그 세 수의 합을 모두 result_list라는 리스트에 담았다.

sorted를 한 경우와 sorted를 하지 않은 경우 모두 result_list의 내용과, 리스트의 길이를 출력해보았다.

 

 

 

1. sorted 하지 않은 경우(오답)

위 두 줄: 입력 값/ 셋째 줄: 리스트 내용/ 넷째 줄: 길이/ 다섯째 줄: 출력 값

 

2. sorted 한 경우(정답)

위 두 줄: 입력 값/ 셋째, 넷째 줄: 리스트 내용/ 다섯째 줄: 리스트 내용/ 여섯째 줄: 출력 값

 

 

확인해보면 sorted를 하지 않았을 경우, m을 넘지 않는 세 수의 모든 조합을 담고있는 result_list에 모든 값이 담기지 못하는 것을 알 수 있다.

다시 말해 세 수의 모든 합이 담기지 못하고, 누락되는 케이스가 발생하고 있다.

 

 

nums를 정렬하지 않는 경우의 nums 리스트 상태이다.

 

정렬되지 않은 nums 리스트

 

 

반복문을 확인해본다.

정렬되지 않은 경우 반복문 시작할 때의 i, j, k의 위치

 

 

위 그림처럼, 반복문을 처음 시작할때 i, j, k는 각각 nums 리스트 내부의 0, 1, 2번 인덱스에 위치할 것인데, 첫 번째 sumOfNums 값 부터 기준치(m)인 500을 넘은 값이 나온다.

 

내가 짠 코드에선 세 수의 합이 500이 넘는 경우 break가 실행되기 때문에 제일 안쪽 반복문(k)를 바로 빠져나오게 된다

즉 누락되는 조합이 발생한 채 j값이 다음 인덱스(2번)로 넘어갈 것이다.

 

따라서 오름차순으로 정렬해야 정상적으로 모든 조합을 체크할 수 있는 것이다.