-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
cutting edge 시간 복잡도 관련
22.04.01 21:17 작성 조회수 102
1
안녕하세요.
소스코드를 보면 지금까지 잔돈의 총 합이 T보다 크면 가지를 치게 구현이 되어있는데, 만약 제가 짠 코드처럼 저런 경우에 추가적으로 앞으로 남은 모든 잔돈의 총 합을 현재 합에 더해도 T보다 작은경우까지 가지를 치게 되면 sum(tot[L:]) 이 파트가 매 재귀함수마다 계산을 하게 되면서 오히려 시간복잡도가 늘어나는지 궁금합니다.
(사실 리스트 인덱싱 및 내장함수 sum을 실행할때 시간복잡도 빅o로 어떤지가 궁금하기도 합니다.)
t = int(input())
k = int(input())
ary = [list(map(int,input().split())) for _ in range(k)]
cnt = 0
tot = [ x[0]*x[1] for x in ary ]
def DFS(L,al):
global cnt
if al == t:
cnt +=1
return
if L == k:
return
if al + sum(tot[L:]) < t or al > t:
return
else:
for i in range(ary[L][1]+1):
DFS(L+1,al + ary[L][0]*i)
DFS(0,0)
print(cnt)
답변을 작성해보세요.
0
답변 1