문제 / 바둑이 승차(DFS, 부분집합) / Python 파이썬

 

문제 제목: 바둑이 승차(DFS)

철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태 울수가 없다. 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다. N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요.

---

기본기 문제에 있는 부분집합 구하기 문제를 참고하였다.

 

먼저 입력받는 값을 구현함

 

arr = [0]
m, n = map(int,input().split())
for _ in range(n):
    arr.append(int(input()))

 

그리고 각각 구한 부분집합들을 저장하기위해 dfs_list 를 선언해주었다. (전역변수로 해서 DFS를 통해 구한 부분집합을 dfs_list안에 넣어 줄 것임)

그리고 나머지 부분은 부분집합의 문제와 동일

 

if __name__ == "__main__":
    dfs_list = []
    arr = [0]
    m, n = map(int,input().split())
    for _ in range(n):
        arr.append(int(input()))
    ch = [0]*(n+1)
    DFS(1)
    print(dfs_list)

dfs 함수 구현 부분

def DFS(v):
    global dfs_list
    global arr
    if v == n+1:
        tmp = [] #부분집합
        for i in range(1, n+1):
            if ch[i] == 1:
                tmp.append(arr[i]) # ch=1이면 해당 값을 포함
        print(tmp)
        dfs_list.append(tmp) 


    else:
        ch[v] = 1 # 해당 값을 부분집합에 포함한다
        DFS(v+1)
        ch[v] = 0 # 해당 값을 포함하지 않음
        DFS(v+1)
        print()

    return dfs_list

 

여기까지 구현하여 출력하면 다음과같이 부분집합이 구해짐을 알 수 있다.

def DFS(v):
    global dfs_list
    global arr
    if v == n+1:
        tmp = []
        for i in range(1, n+1):
            if ch[i] == 1:
                tmp.append(arr[i])
        print(tmp)
        dfs_list.append(tmp)


    else:
        ch[v] = 1
        DFS(v+1)
        ch[v] = 0
        DFS(v+1)
        print()

    return dfs_list

if __name__ == "__main__":
    dfs_list = []
    arr = [0]
    m, n = map(int,input().split())
    for _ in range(n):
        arr.append(int(input()))
    ch = [0]*(n+1)
    DFS(1)
    print(dfs_list)

해당 부분집합에서 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다 는 조건만 완성하면 된다.

따라서 부분집합에서 C값을 넘는 것 dfs list 에 포함하지 않는다.

(코드 상에서 C값은 m으로 표현했다.)

 

if sum(tmp) < m:
    dfs_list.append(tmp)

 

마지막에 부분집합의 합을 계산하여 최대를 출력하는 코드 작성

sum_list = []
for i in dfs_list:
    sum_list.append(sum(i))

print(max(sum_list))

 

 

나의 풀이

import sys

def DFS(v):
    global dfs_list
    global arr
    if v == n+1:
        tmp = []
        for i in range(1, n+1):
            if ch[i] == 1:
                tmp.append(arr[i])

        if sum(tmp) < m:
            dfs_list.append(tmp)


    else:
        ch[v] = 1
        DFS(v+1)
        ch[v] = 0
        DFS(v+1)

    return dfs_list

if __name__ == "__main__":
    dfs_list = []
    arr = [0]
    m, n = map(int,input().split())
    for _ in range(n):
        arr.append(int(input()))
    ch = [0]*(n+1)
    DFS(1)

    sum_list = []
    for i in dfs_list:
        sum_list.append(sum(i))

    print(max(sum_list))

시간초과... 아마 저장도 많이하고 for문도 많아서 그런듯

---

 

 

모범답안

 

import sys
from collections import deque

def DFS(L, sum):
    global result
    # L : 인덱스 번호
    # sum: 부분집합 합

    if L == n: # 종착점에 온 것. 부분 집합 하나가 만들어진 종학점
        if sum > result:
            result = sum
    else:
        DFS(L+1, sum+a[L]) # a[l]번째를 부분집합으로 참여
        DFS(L+1, sum) # a[l]번째를 부분집합으로 참여시키지 않음




if __name__ == "__main__":
    c,n = map(int,input().split())
    a = [0] * n
    result = -2147000000 # 답을 저장 (초기화는 가장 작은 값으로)
    arr = [0]

    for i in range(n):
        a[i] = int(input())

    DFS(0,0)
    print(result)

 

import sys
from collections import deque

def DFS(L, sum):
    global result
    # L : 인덱스 번호
    # sum: 부분집합 합
    if sum > c:
        return # 무게제한

    if L == n: # 종착점에 온 것. 부분 집합 하나가 만들어진 종학점
        if sum > result:
            result = sum
    else:
        print("index: ", L,", Sum: ", sum,", a[L]: ", a[L], ", sum + a[L]: ", sum + a[L])
        DFS(L+1, sum+a[L]) # a[l]번째를 부분집합으로 참여 (바둑이 더 태운다)
        DFS(L+1, sum) # a[l]번째를 부분집합으로 참여시키지 않음 (바둑이 태우지마!)




if __name__ == "__main__":
    c,n = map(int,input().split())
    a = [0] * n
    result = -2147000000 # 답을 저장 (초기화는 가장 작은 값으로)
    arr = [0]

    for i in range(n):
        a[i] = int(input())

    DFS(0,0)
    print(result)
'''
259 5
81
58
42
33
61
'''

출력 결과

index:  0 , Sum:  0 , a[L]:  81 , sum + a[L]:  81
index:  1 , Sum:  81 , a[L]:  58 , sum + a[L]:  139
index:  2 , Sum:  139 , a[L]:  42 , sum + a[L]:  181
index:  3 , Sum:  181 , a[L]:  33 , sum + a[L]:  214
index:  4 , Sum:  214 , a[L]:  61 , sum + a[L]:  275
index:  4 , Sum:  181 , a[L]:  61 , sum + a[L]:  242
index:  3 , Sum:  139 , a[L]:  33 , sum + a[L]:  172
index:  4 , Sum:  172 , a[L]:  61 , sum + a[L]:  233
index:  4 , Sum:  139 , a[L]:  61 , sum + a[L]:  200
index:  2 , Sum:  81 , a[L]:  42 , sum + a[L]:  123
index:  3 , Sum:  123 , a[L]:  33 , sum + a[L]:  156
index:  4 , Sum:  156 , a[L]:  61 , sum + a[L]:  217
index:  4 , Sum:  123 , a[L]:  61 , sum + a[L]:  184
index:  3 , Sum:  81 , a[L]:  33 , sum + a[L]:  114
index:  4 , Sum:  114 , a[L]:  61 , sum + a[L]:  175
index:  4 , Sum:  81 , a[L]:  61 , sum + a[L]:  142
index:  1 , Sum:  0 , a[L]:  58 , sum + a[L]:  58
index:  2 , Sum:  58 , a[L]:  42 , sum + a[L]:  100
index:  3 , Sum:  100 , a[L]:  33 , sum + a[L]:  133
index:  4 , Sum:  133 , a[L]:  61 , sum + a[L]:  194
index:  4 , Sum:  100 , a[L]:  61 , sum + a[L]:  161
index:  3 , Sum:  58 , a[L]:  33 , sum + a[L]:  91
index:  4 , Sum:  91 , a[L]:  61 , sum + a[L]:  152
index:  4 , Sum:  58 , a[L]:  61 , sum + a[L]:  119
index:  2 , Sum:  0 , a[L]:  42 , sum + a[L]:  42
index:  3 , Sum:  42 , a[L]:  33 , sum + a[L]:  75
index:  4 , Sum:  75 , a[L]:  61 , sum + a[L]:  136
index:  4 , Sum:  42 , a[L]:  61 , sum + a[L]:  103
index:  3 , Sum:  0 , a[L]:  33 , sum + a[L]:  33
index:  4 , Sum:  33 , a[L]:  61 , sum + a[L]:  94
index:  4 , Sum:  0 , a[L]:  61 , sum + a[L]:  61
242

Process finished with exit code 0

이것두 시간 초과한다.. 

 

그렇다면 방법은 조금 더 Cut Edge 한다는 것!

바둑이를 태운다, 안태운다에 대한 상태트리

남은 바둑이들을 다 더하더라도 해당 더한 값이 result보다 작아지면 cut 한다.

그렇게 컷하면 됨

 

sum : 현재까지 더한 값

total: 바둑이 전체를 더한 값

tsum: 이미 태운 바둑이들의 합

 

total - tsum: 앞으로 태울 바둑이들

 

sum + (total - tsum): 현재 바둑이들 합 + 앞으로 태울 남은 바둑이들 합

 

현재 바둑이들 합 + 앞으로 태울 남은 바둑이들 합이 result ( 부분집합의 최댓값 ) 보다 적다면

함수 종료

 

(가지치기 푸루닝~)

 

def DFS(L, sum,tsum):
    global result
    # L : 인덱스 번호
    # sum: 부분집합 합
    if sum + (total - tsum) < result :# 앞으로 판단해야할 바둑이들의 합이 result 보다 적더라 -> 가지 뻗을 필요가 없음
        return
    if sum > c:
        return # 무게제한

    if L == n: # 종착점에 온 것. 부분 집합 하나가 만들어진 종학점
        if sum > result:
            result = sum
    else:
        print("index: ", L,", Sum: ", sum,", a[L]: ", a[L], ", sum + a[L]: ", sum + a[L])
        DFS(L+1, sum+a[L],tsum + a[L]) # a[l]번째를 부분집합으로 참여
        DFS(L+1, sum,tsum + a[L]) # a[l]번째를 부분집합으로 참여시키지 않음




if __name__ == "__main__":
    c,n = map(int,input().split())
    a = [0] * n
    result = -2147000000 # 답을 저장 (초기화는 가장 작은 값으로)
    arr = [0]

    for i in range(n):
        a[i] = int(input())
    total = sum(a)
    DFS(0,0,0)
    print(result)

 

출력 결과

index:  0 , Sum:  0 , a[L]:  81 , sum + a[L]:  81
index:  1 , Sum:  81 , a[L]:  58 , sum + a[L]:  139
index:  2 , Sum:  139 , a[L]:  42 , sum + a[L]:  181
index:  3 , Sum:  181 , a[L]:  33 , sum + a[L]:  214
index:  4 , Sum:  214 , a[L]:  61 , sum + a[L]:  275
index:  4 , Sum:  181 , a[L]:  61 , sum + a[L]:  242
242

 

ㅊ

---

※ 알아야 할 것

- 적절한 DFS 의 가지치기가 필요하당