[SWEA][D4] 1486. 장훈이의 높은 선반 D4 파이썬

 

📖 [D4] 1486. 장훈이의 높은 선반 D4 파이썬

 

풀이 >>부분집합을 구하고, 합을 구하고, 적절한 값을 찾기 위해 비교하기

 

하지만, 1단계부터 모르겠다. 엉엉. 방법은 많긴 많지... 모가몬지... 

부분집합 구하기 중 하나 골라서 풀어봤는데 아예 샘플 테스트케이스부터 시간초과 거절을 당하고. 일단 재귀를 이용했는데 이걸 뭐라하는지 모르겠다... 다른 풀이들에 대해서도 연구를 다시 해야 한다.

 

 

� <일단 PASS>

# 1486. 장훈이의 높은 선반 D4
# 2020.02.27 오후 11시
'''
1. 첫 줄에는 점원의수 N, 선반의높이 B(1 ≤ N ≤ 20, 1 ≤ B ≤ S)
S는 두 번째 줄에서 주어지는 점원들 키의 합이다.
2. 둘 줄에는 N개의 각 정수는 각 점원의 키 Hi (1 ≤ Hi ≤ 10,000)
'''
 
# find_solution(items원배열   , B비교값 ,   수 0,        수 0,총최대값sum(items))
def find_solution(origin_items, goal_sum,next_idx, current_sum, current_best_sum):
    # 재귀 마지막 도달 조건. i+1로 더이상 확인해 볼 범위를 넘을 때
    if next_idx == len(origin_items):
        return current_best_sum
 
    for i in range(next_idx, len(origin_items)): # 처음은 0부터~끝까지, 다음은 +1부터... 
        item = origin_items[i]
        current_sum += item # 들어가려고 합 +
       
        # 리턴할 목표 값이 되려면,.. 지금합계값이 총최대값보다 작으면서 비교값보다 같거나커야한다.
        if goal_sum <= current_sum < current_best_sum:
            current_best_sum = current_sum
 
        # 재귀.  # i+1 원배열 안에 다음인덱스로 재귀    
        current_best_sum = find_solution(origin_items, goal_sum,i + 1, current_sum, current_best_sum)
        current_sum -= item # 빠져나오면서 차 -
 
    # 원하는 건 가장 적절한 합계 값(비교값과의 차이가 가장 근소한 것)
    return current_best_sum
 
 
T = int(input())
for tt in range(1, T + 1):
    N, B = map(int, input().split())  # 점원의수 N, 선반의높이 B
    items = list(map(int, input().split()))
    items.sort()
    result = find_solution(items, B, 0, 0, sum(items))
    print("#{} {}".format(tt, result-B))  # 결과 : 적절한 합계 - 비교값의 차이
 
 

 

✍ <구조>

 

✍ <설명>

# 구조 설명을 위한 예시 :: 부분집합 합을 이루는 부분집합subset  전부 볼 수 있게 함
# 1486. 장훈이의 높은 선반 D4
# 2020.02.27 오후 11시
'''
1. 첫 줄에는 점원의수 N, 선반의높이 B(1 ≤ N ≤ 20, 1 ≤ B ≤ S)
S는 두 번째 줄에서 주어지는 점원들 키의 합이다.
2. 둘 줄에는 N개의 각 정수는 각 점원의 키 Hi (1 ≤ Hi ≤ 10,000)
'''
 
# find_solution(items원배열   , B비교값 ,부분집합,    수 0,        수 0,총최대값sum(items))
def find_solution(origin_items, goal_sum, subset, next_idx, current_sum, current_best_sum):
    # 재귀 마지막 도달 조건. i+1로 더이상 확인해 볼 범위를 넘을 때
    if next_idx == len(origin_items):
        print("끝",current_best_sum)
        return current_best_sum
 
    for i in range(next_idx, len(origin_items)): # 처음은 0부터~끝까지, 다음은 +1부터... 
        item = origin_items[i] 
        subset.append(item)
        current_sum += item # 들어가려고 합 +
        print("깊이{}번째 find_solution의 for idx={}: ".format(next_idx, i), subset, current_sum)
        
        # 리턴할 목표 값이 되려면,.. 지금합계값이 총최대값보다 작으면서 비교값보다 같거나커야한다.
        #if goal_sum <= current_sum < current_best_sum:
        if current_sum >= goal_sum and current_sum < current_best_sum:
            current_best_sum = current_sum
            print("UPDATE!", current_sum)
 
        # 재귀.   
        current_best_sum = find_solution(origin_items, goal_sum, subset, i + 1, current_sum, current_best_sum) 
        current_sum -= item # 빠져나오면서 차 -
        subset.pop()
        print("이상적합:",current_best_sum)
 
    # 원하는 건 가장 적절한 합계 값(비교값과의 차이가 가장 근소한 것)
    return current_best_sum
 
 
T = 1
for tt in range(1, T + 1):
    N, B = 3, 12
    items = [3,6,9]
    items.sort()
    result = find_solution(items, B, [], 0, 0, sum(items)) 
    print("#{} {}".format(tt, result-B)) # 결과 : 적절한 합계 - 비교값의 차이
 
 
 
 

 

 

끝!

---

👀 후기) 

 

<대실패> 이 부분집합 구하기 구조를 아예 버리자 ... 마음이 아프다...

답은 나오긴 나오는데... 점원의 수N이 10정도가 넘어가는 경우, 너무나도 오래걸린다. 

# 부분집합 구하면서 바로 합계
def get_power_set(s):
    power_set=[[]]
    for elem in s:
        for sub_set in power_set:
            power_set = power_set +[list(sub_set)+[elem]] # 이게 추후 오래 걸려서 문제
    return power_set
 
print(get_power_set([3,6,9])
 
 

## 대실패. 시간초과. 점원의수가 10이 넘어가자 몹시 느려짐. 
# 장훈이의 높은 선반 D4
# 2020.02.27 오후 3시
# 시간 :분 (해석및연습:분,설계및구현:분)
'''
1. 첫 줄에는 점원의수 N, 선반의높이 B(1 ≤ N ≤ 20, 1 ≤ B ≤ S)
S는 두 번째 줄에서 주어지는 점원들 키의 합이다.
2. 둘 줄에는 N개의 각 정수는 각 점원의 키 Hi (1 ≤ Hi ≤ 10,000)
'''
import sys
sys.stdin = open("inputput.txt")

T = int(input()) # 테스트케이스 T
for t in range(1,T+1):
    n,b = map(int,input().split())
    ki = list(map(int,input().split()))
    
    # 부분집합 별 합계
    def add(s):
        arr = [[]]
        ad = 0
        for i in range(len(s[0])):
            ad += s[0][i]
        arr[0].append(ad)
        return arr
    # 부분집합 구하면서 바로 합계(이러면 빨라질줄 알았다..)
    def get_power_set(s):
        power_set=[[]]
        for elem in s:
            for sub_set in power_set:
                power_set = power_set +add([list(sub_set)+[elem]]) # 리스트더하기는 몹시...
        return power_set
    
    ki.sort() # 입력 리스트 오름차순 정렬
    ret = get_power_set(ki)
    ret.sort() # 합계 리스트 오름차순 정렬

    r = ret[len(ret)-1][0]
    for i in range(1,len(ret)):
        if b - ret[i][0] <= 0 and r >= abs(b-ret[i][0]):
            r = abs(b-ret[i][0])
            break # ret.sort() 합계 리스트 오름차순 정렬 하지 않으면, 전부 돌아야한다
    print('#{} {}'.format(t,r))

 

10개 테스트 케이스 중에서 8개만 돌아가고 제한시간초과.. 제출을 아예 못하게 샘플부터 거부 ㅋㅋㅋ

---

📌 문제 출처

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw

SW Expert Academy

 

 

 

---

📌 참조

https://cnpnote.tistory.com/entry/PYTHON-%EC%84%B8%ED%8A%B8%EC%9D%98-%EB%AA%A8%EB%93%A0-%EB%B6%80%EB%B6%84-%EC%A7%91%ED%95%A9%EC%9D%84-%EC%96%BB%EB%8A%94-%EB%B0%A9%EB%B2%95-powerset

[PYTHON] 세트의 모든 부분 집합을 얻는 방법? (powerset)

---

유 : 백트래킹 방식으로 이용하면 풀수있습니다. 현재 조합을 구하는 방식이 어려우신것 같습니다. 백준의 N과 M을 풀면서 익혀보세요

 

셩 : 이 문제는 재귀를 통해서 점원을 한 명씩 선택하면서 더해줘야합니다 부분집합을 구하는 방법으로는 시간초과가 날거에요 조만간 풀이 올리겠습니다~