알고리즘/문제풀이

비트마스킹(캠프 준비 / G5) - 16938

문승주 2023. 7. 18. 20:35
반응형

1. 문제

알고리즘 캠프를 열려면 많은 준비가 필요하다. 그 중 가장 중요한 것은 문제이다. 오늘은 백준이를 도와 알고리즘 캠프에 사용할 문제를 고르려고 한다.

백준이는 문제를 N개 가지고 있고, 모든 문제의 난이도를 정수로 수치화했다. i번째 문제의 난이도는 Ai이다.

캠프에 사용할 문제는 두 문제 이상이어야 한다. 문제가 너무 어려우면 학생들이 멘붕에 빠지고, 문제가 너무 쉬우면 학생들이 실망에 빠지게 된다. 따라서, 문제 난이도의 합은 L보다 크거나 같고, R보다 작거나 같아야 한다. 또, 다양한 문제를 경험해보기 위해 가장 어려운 문제와 가장 쉬운 문제의 난이도 차이는 X보다 크거나 같아야 한다.

캠프에 사용할 문제를 고르는 방법의 수를 구해보자.

 

2. 입력

첫째 줄에 N, L, R, X가 주어진다.

둘째 줄에는 문제의 난이도 A1, A2, ..., AN이 주어진다.

3 5 6 1
1 2 3

 

4 40 50 10
10 20 30 25

 

5 25 35 10
10 10 20 10 20

 

3. 출력

캠프에 사용할 문제를 고르는 방법의 수를 출력한다.

2

 

2

 

6

 

4. 코드

import sys
from itertools import combinations

input = sys.stdin.readline

n, l, r, x = map(int, input().split())

papers = list(map(int, input().split()))
result = 0

for i in range(n-1):
  for paper in combinations(papers,i+2):
    if l <= sum(paper) <= r and max(paper)-min(paper) >= x:
      result += 1
      
print(result)

 

5. 풀이설명

① 입력받을 길이 "n" 과 최솟값 "l" 최댓값 "r" 최소차 "x"를 입력받는다.

 

②  n길이의 배열 입력값을 papers를 입력받는다.

 

③ 결과값 result를 0으로 선언한다.

 

④ n-1만큼 반복문을 실행한다.

 

⑤ combinations 함수를 사용하여 papers로 이루어진 i+2개의 조합으로 반복문을 실행한다.

 

⑥ 조합 paper의 합이 l보다 크거나 같고 r보다 작거나 같고 paper의 최댓값과 최솟값의 차이가 x보다 크거나 같으면 result 결과값에 1을 추가한다.

 

⑦ 결과값 result를 출력한다.

 

6. 느낀점

결국 혼자 못풀었는데 combinations 만 사용 했으면 쉽게 풀 수 있는 문제였다. 배열의 조합을 구해주는 함수인데 꼭 기억하자!

반응형