[BOJ / 백준] 16938번 캠프 준비 파이썬(Python) 문제 풀이

 

문제

 

문제 링크 : https://www.acmicpc.net/problem/16938

16938번: 캠프 준비

 

 

 

 

 

CODE

import sys
from itertools import combinations

n, l, r, x = map(int, input().split())
a = list(map(int, sys.stdin.readline().split()))
result = 0

a.sort()

for i in range(n - 1):
    for j in range(n - 1, i, -1):
        if a[j] - a[i] >= x:
            for k in range(j - i):
                for m in combinations(a[i + 1:j], k):
                    sum = a[i] + a[j]
                    for item in m:
                        sum += item
                    if l <= sum <= r:
                        result += 1

print(result)

 

 

 

 

 

풀이

💡 idea

- 난이도를 오름차순으로 정렬

- 문제 두 개를 골라서 난이도 차이 x에 대한 검증을 먼저 한다

- 두 문제 사이에서 0개 이상의 문제를 골라 난이도의 합을 구하고 L과 R 사이에 있음을 검사하고 결과를 증가시킨다

 

💡 implement

for m in combinations(a[i + 1:j], k):
    sum = a[i] + a[j]
    for item in m:
        sum += item

combinations를 통해 두 문제 사이의 조합을 구한다

 

 

 

 

 

결과