(백준) 6148번: Bookshelf 2 파이썬 풀이

<포스팅 요약>

1. 문제풀러가기

2. 문제 해결 코드

3. 로직 분석

---

1. 문제풀러가기

https://www.acmicpc.net/problem/6148

6148번: Bookshelf 2

 

문제 해석:

- 소를 쌓아서 책꽂이 높이보다 크거나 같게 만들기.

- 쌓은 소의 높이와 책꽂이 높이의 최소 차를 구하기 => min(쌓은 소의 높이 - 책꽂이 높이 )

---

2. 문제 해결 코드

코드 (성공)

import sys
from itertools import combinations

input = sys.stdin.readline
n, b = map(int, input().split())
arr = [int(input()) for _ in range(n)]
num = 10000000000001

for i in range(1, n+1):
    lst = list(combinations(arr, i))
    for j in lst:
        sum_num = sum(j)
        if sum_num >= b:
            num = min(num, sum_num)
print(num-b)

 

시간 초과인 코드 (실패)

import sys
input = sys.stdin.readline
n, b = map(int, input().split())
arr = [int(input()) for _ in range(n)]
num = 10000000000001
visited = [False for _ in range(n)]

def dfs(cnt):
    global num, arr
    if cnt >= b:
        num = min(cnt, num)
        return

    for k in range(n):
        if visited[k] == False:
            cnt += arr[k]
            visited[k] = True
            dfs(cnt)
            cnt -= arr[k]
            visited[k] = False

dfs(0)
print(num-b)

 

처음에, 알고리즘으로 구현하고 싶어서 dfs로 구현했더니 시간초과가 떳다... 

그래서 그냥 combinations 사용했더니 바로 통과.

 

* combinations에 대해서 알고 싶다면 아래 링크 참고해주세요

2021.06.18 - [(Python)파이썬/(Python)파이썬 문법] - (파이썬) 리스트 요소 조합하기/ permutations & combinations

(파이썬) 리스트 요소 조합하기/ permutations & combinations

 

---

3. 로직분석

간단하다, 그냥 리스트의 모든 가능한 조합들을 만들고.

(조합된 것들의 합) - (책장의 높이가 가장 작은 값) 을 출력해주면 끝!!!

 

예)

- cows_height = [3,1,5]이고 bookshelf_height = 7일때, combinations를 사용하면 , 

- [(3),(1),(5),(3,1),(3,5),(1,5),(3,1,5)] 이렇게 조합할 수 있다.

- 3-7 = -4 이므로 조건에서 마이너스는 안된다 하였으니 탈락

- 1-7 = -6 마찬가지로 탈락

- 5-7 = -2 탈락

- (3+1)-7 = -3 탈락

- (3+5)-7 = 1 합격

- (1+5)-7 = -1 탈락

- (3+1+5)-7 = 4 합격

 

(3,5)와 (3,1,5) 이 두 조합만 사용할 수 있다.

하지만 (3,5) 조합이 (3,1,5)보다 책꽂이 높이와의 차가 작으므로(  (3+5)-7 <  (3+1+5)-7 ),

(3+5)-7 = 1 

최종적으로 1 을 출력해준다.