[SW] [DFS] [조합] 9229. 한빈이와 Spot Mart

9229. 한빈이와 Spot Mart

SW Expert Academy

 

• 내 풀이
  • 정렬 후 맨앞, 맨뒤값 합해가면서 
  • 합보다 넘어가면 lpoint -1
  • 합보다 작거나 같으면 fpoint+1

#최대 무게 합 출력
#2봉지만 사야함

T=int(input())
for tc in range(1,T+1):
    #과자봉지 개수n, 무게 합 제한 m
    n,m=map(int,input().split())
    snack=list(map(int,input().split()))
    snack.sort()

    ssum=0
    fpoint=0
    lpoint=n-1

    while fpoint<lpoint:
        print(fpoint, lpoint)
        front=snack[fpoint]
        last=snack[lpoint]
      
        if front+last>m:
            lpoint-=1
            continue

        #넘지않는 경우
        ssum=max(ssum, front+last)
        fpoint+=1

    if ssum==0:
        ssum=-1
    print("#{} {}".format(tc, ssum))

 

• 다른 사람 풀이
  • 수정할 필요없이 처음 생성 시 max=-1 해놓으면 됨
  • 조합, dfs
    • 여러개 중 2봉지만 조합해서 sum 계산

#최대 무게 합 출력
#2봉지만 사야함


T=int(input())
for tc in range(1,T+1):
    #과자봉지 개수n, 무게 합 제한 m
    n,m=map(int,input().split())
    snack=list(map(int,input().split()))
    maxSum=-1
  
    def dfs(depth, sum, start):
        global maxSum
        if depth==2: #두봉지 선택되면
            if sum>m:
                return
            maxSum=max(maxSum, sum)
            return

        for i in range(start, n):
            dfs(depth+1, sum+snack[i], i+1)

    dfs(0,0,0)
    print("#{} {}".format(tc, maxSum))