[Python, 파이썬] SWEA 9229. 한빈이와 Spot Mart

한빈이가 들고 다닐수 있는 과자들의 최대 무게 합을 구하는 문제.

 

 

T = int(input()) # 테스트케이스의 개수 T

for test_case in range(1, T+1):

    N, M = map(int, input().split()) # 과자 봉지의 개수 N, 무게 합 제한 M
    snack = list(map(int, input().split())) # N개의 과자 봉지 무게

    max_ = -1

    for i in range(N-1):
        for j in range(i+1, N):
            if(snack[i]+snack[j] <= M): # M그램 이하일때
                max_ = max(max_, snack[i]+snack[j]) # 최대값 업데이트

    print("#%d %d" %(test_case, max_))

 

 

 

[문제풀이]

---

 

언어 선택에 python이 없지만 일단 python으로 풀었다.

처음엔 바로 완전탐색이 떠올랐으나 선택할 수 있는 과자 봉지의 수가 정확히 정해져 있다.

 

이 경우, 완전 탐색을 할 필요없이 그저 과자 봉지 중 2개를 선택해 그 중 M 이하의 최댓값을 탐색하는 조합 문제다.

 

if(snack[i]+snack[j] <= M): # M그램 이하일때
    max_ = max(max_, snack[i]+snack[j]) # 최대값 업데이트

 

그래서 이중 for문을 돌려 M 이하일 경우 최댓값을 업데이트 해주면 끝!

이때 max_에는 -1을 초기값으로 지정해 들고 갈 수 있는 과자 봉지가 없을 때(=업데이트가 없을 경우) -1을 출력되도록 한다.