[SWEA] 한빈이와 Spot Mart - python

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AW8Wj7cqbY0DFAXN&categoryId=AW8Wj7cqbY0DFAXN&categoryType=CODE&problemTitle=&orderBy=SUBMIT_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=2

SW Expert Academy

 

풀고보니 파이썬 제출이 없어서 채점을 진행하지 못한 문제

 

DFS로 길이가 2개인 부분집합을 생성해서 합을 비교해서 answer을 도출하는 방식으로 풀었다.

가지치기를 안해서 아마 시간초과가 날 가능성이 높다. 

T = int(input())


def DFS(L, s, k):
    global answer
    if L == n:
        return
    else:
        if k==2:
            if m >= s:
                if answer <= s:
                    answer = s
        DFS(L+1, s+arr[L], k+1)
        DFS(L+1, s, k)

for _ in range(T):
    n, m = map(int, input().split())
    arr = list(map(int, input().split()))
    answer = -1
    DFS(0, 0, 0)
    print(f'#{_+1} {answer}')

 

완성

SWEA 문제 너무 좋다.