[백준] 2798번 - 블랙잭

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

 

✔️ 문제

 

 

문제는 다음과 같다.

 

 

✔️ 풀이

 

 

문제가 굉장히 재밌었는데,

주어진 카드 수 중 3가지 조합이 M이랑 같으면 M을 출력하고,

M이랑 같지 않으면 M을 넘지 않는 선에서 가장 큰 수를 출력하면 된다.

 

import sys
input = sys.stdin.readline

n,m=map(int,input().split())
card=sorted(list(map(int,input().split())), reverse=True)
x=0
data=[]

for i in range(n-1):
    if i+2==n:
        break
    for j in range(i+2, n):
        if card[i]+card[i+1]+card[j]==m:
            x=m
        elif card[i]+card[i+1]+card[j]<m:
            data.append(card[i]+card[i+1]+card[j])
if x==m:print(m)
else:print(max(data))

 

처음에는 다음과 같이 생각을 했는데,

예제 1과 2는 맞게 되지만 큰 수부터 역으로 들어온 반례에 대해서는

앞 두 숫자가 붙어있는 인덱스에 숫자만 더하는 형식이라

11%에서 오답처리가 된다.

 

import sys
input = sys.stdin.readline

n,m=map(int,input().split())
card=sorted(list(map(int,input().split())))
data=[]

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

if max(data) == m: print(m)
else: print(max(data))

 

그래서 다음처럼 인덱스에 붙은 것끼리 더하는 것이 아닌

순차적으로 j와 k를 증가시키는 형태로 작성해야 한다.

 

또한, 위 코드의 시간을 더 단축시키기 위해서는

append를 사용하지 않고 출력해야 한다.

 

import sys
input = sys.stdin.readline

n,m=map(int,input().split())
card=sorted(list(map(int,input().split())), reverse=True)
x=0

for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            num = card[i]+card[j]+card[k]
            if num <= m: 
                if x < num: x = num
                break

print(x)

 

최종적으로 다음과 같이 append를 사용하지 않고

바로 0으로 선언한 x에 값을 담아주어 출력하게 하였다.

3가지 조합 숫자가 m보다 작거나 같을때,

x가 해당 숫자보다 작으면 x에 값을 담아주는 것이다.

 

나에게는 이런 문제 유형이 재밌는 것 같다.

화이팅 💪