바둑이 승차 (Cut Edge Tech)

인프런 김태원님의 파이썬 알고리즘 문제풀이를 듣고 작성한 글입니다.

https://inf.run/8dBY

파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의

내 풀이 (정답아님)

#내 풀이
def DFS(L, sum):
    global maxx
    if L == n-1:
        if sum < c and sum > maxx:
            maxx = sum
            print(maxx)
    else:
        DFS(L+1, sum+a[L])
        DFS(L+1, sum)

if __name__ == "__main__":
    c, n = map(int, input().split())
    a = []
    maxx = 0
    for i in range(n):
        a.append(int(input()))
    a.sort(reverse=True)
    DFS(0, 0)

예제를 통과하고

제출하여 채점했더니 전부 오답이 나왔다 ㅋ.ㅋ

 

강의 풀이 - 처음 방안

#강의 풀이
def DFS(L, sum):
    global result
    if sum > c:
        return
    if L == n:
        if sum > result:
            result = sum
    else:
        DFS(L+1, sum+a[L])
        DFS(L+1, sum)

if __name__ == "__main__":
    c, n = map(int, input().split())
    a = [0] * n
    result = -2147000000
    for i in range(n):
        a[i] = int(input())
    DFS(0, 0)
    print(result)

이 코드를 구성하면 4, 5번 테스트 케이스에서 시간초과가 발생한다.

따라서, if sum > c: 이외에도 시간을 더 줄이기위해 cut 조건을 발견해야 한다.

 

강의 풀이 - cut 조건 추가

#강의 풀이
def DFS(L, sum, tsum):
    global result
    if sum + (total-tsum) < result:
        return
    if sum > c:
        return
    if L == n:
        if sum > result:
            result = sum
    else:
        DFS(L+1, sum+a[L], tsum+a[L])
        DFS(L+1, sum, tsum+a[L])

if __name__ == "__main__":
    c, n = map(int, input().split())
    a = [0] * n
    result = -2147000000
    for i in range(n):
        a[i] = int(input())
    total = sum(a)
    DFS(0, 0, 0)
    print(result)

tsum 이라는 변수를 추가한다.

tsum은 트럭에 태운 바둑이가 아니고,

거쳐지나간 모든 바둑이의 무게의 합을 담는다.

 

total - tsum = 앞으로 적용할 아래 노드들의 무게 라고 볼 수 있다.

만약 트럭에 태운 바둑이 sum의 무게 + (total - tsum)를 했을때

그 값이 이미 result 의 최대값보다 작다면 그 아래 노드는 이미 볼 필요가 없기때문에

시간 단축이 크게 가능하다.

 

흠..어렵군