100일 동안 매일 알고리즘을 하면? - 7일차

100일 동안 매일 알고리즘을 하면? - 7일차

오늘 어제 코드포스에서 못푼 문제를 풀었다.

 

https://codeforces.com/contest/1622/problem/C

Problem - C - Codeforces

 

Set 을 하는 경우와 Decrease 를 하는 모든 경우를 탐색했더니 시간초과가 났다.

그럴만한게 시간복잡도가 2^n 이다.

그래서 다른 사람들의 코드를  보았는데 이해하지 못하겠다. 무슨말인지.

 

import copy
from collections import deque
t = int(input())

cnt = 0
ret = 0
for _ in range(t):
    n, k = map(int, input().split())
    array = list(map(int, input().split()))
    queue = deque()
    queue.append((cnt, array))
    while(queue):
        nowItem = queue.popleft()
        nowCnt, nowArr = nowItem
        if (sum(nowArr) <= k):
            ret = nowCnt
            break
        nowArr.sort()
        for i in range(2):
            if (i == 0):  # set
                newArr = copy.deepcopy(nowArr)
                newArr[-1] = newArr[0]
                queue.append((nowCnt + 1, newArr))
            if (i == 1):  # decrease
                newArr2 = copy.deepcopy(nowArr)
                newArr2[0] -= 1
                queue.append((nowCnt + 1, newArr2))
    print(ret)