[BOJ] 16938 캠프 준비

thoho·2023년 1월 20일
0

코딩 문제 풀이

목록 보기
9/13

16938 캠프 준비 문제 링크
문제 풀이 코드 링크

문제 풀이 방법이 2개... 비스마스킹 여부에 따라 풀이를 2개로 나누어 풀었다.

문제 요약

첫 줄에 N, L, R, X를 받고, 두번째 줄에 N개의 문제(난이도)가 주어진다.
N개의 문제들 중 문제를 선택하는데, 선택된 문제들의 합은 L보다 크거나 같고 R보다 작거나 같아야한다. 가장 난이도가 높은 문제와 가장 난이도가 낮은 문제의 차가 X보다 크거나 같아야한다.
해당 조건을 만족하는 문제들을 선택하는 방법의 수를 출력한다.


풀이 1 : 비트마스킹 없이

아이디어

전부 검토하면 시간초과가 발생할 것 같아 검사할 필요 없는 경우를 제거하기 위한 방법을 고민해보았다.
난이도의 최대값과 최소값의 차가 X보다 크거나 같아야한다는 점에 착안하여, 최대값과 최소값을 고정하여 그 범위 내의 난이도의 문제들을 선택, 검토하는 방식으로 구현하였다.

예시

[15, 20, 25, 30]가 있고 X10일 때, 15를 최소값, 25를 최대값으로 고정해 그 사이에 있는 20을 추가한 경우, 추가하지 않은 경우에 대해 각각 검토한다. 이후 15, 30에 대해 검토, 20, 30에 대해 검토한 경우에 따라 경우의 수를 계산한다.

  1. 문제들의 난이도에 대하여 오름차순으로 정렬한다.
  2. i0부터, ji+1부터 증가시키며 problems[j]-problems[i] >= X를 만족하는 경우에 대해, i부터 j 사이에 있는 값들에 대한 조합으로 그 합계가 조건을 만족하는지 검토한다(problems[i]problems[j]는 무조건 포함).
  3. problems[j]-problems[i] >= X를 만족하는 동안 j를 증가시킨다.
  4. 만족되지 않을 경우 i1씩 증가시켜 2를 반복한다.

구현

import sys
import heapq
from collections import deque

input = sys.stdin.readline

# i부터 j까지의 원소의 조합을 선택하여, 조건을 만족하는 경우의 수를 반환.
# curSum은 여태까지 선택한 숫자의 합을 넘김.
def findSet(i, j, curSum) :
  if i > j :
    if curSum >= L and curSum <= R :
      return 1
    else :
      return 0

  if curSum > R :
    return 0
  
  result = 0
  result += findSet(i + 1, j, curSum + questions[i])
  result += findSet(i + 1, j, curSum)

  return result

N, L, R, X = map(int, input().split(" "))

questions = []
questions = list(map(int, input().split(" ")))
questions.sort()

j = 0
result = 0

for i in range(N) :
  j = i + 1
  while j < N and questions[j] - questions[i] < X :
    j += 1
  
  while j < N :
    curSum = questions[i] + questions[j]
    result += findSet(i+1, j-1, curSum)
    j += 1

print(result)

풀이 2 : 비트마스킹 적용

아이디어

시간을 줄이려다가.. 오히려 복잡해졌다는 것을 깨달았다...
같이 문제 푼 친구가 푼 방법을 보니까, 그냥 모든 조합의 경우에 대해 검사를 해도 시간초과가 나지 않는다는 사실을... 생각해보니 1번 풀이도 정렬을 하는 과정에서 시간을 많이 쓴다는 사실을...

1번에서 조합을 찾아내기 위해 재귀적으로 i+1, j-1에 대해 반복 수행을 하며 조합의 경우를 찾아냈는데, 비트마스킹으로 이를 간단히 구현해낼 수 있었다.

1에 대해 문제의 개수 N만큼 왼쪽으로 SHIFT 연산을 한 후, 해당 수에서 1을 빼면 N개의 비트가 1인 형태의 이진수를 얻을 수 있다. (그 예로, (1 << 4) - 1을 하면 0b1111이 된다)
각각의 비트가 해당 문제를 포함하는지 아닌지를 선택한다. 1인 경우 해당 문제를 포함하고, 0인 경우 해당 문제를 포함하지 않는다.

해당 수를 1씩 줄여가며 조건을 만족하는지의 여부를 검사하면 모든 경우에 대해 검사가 가능하다.

구현

import sys
input = sys.stdin.readline


def solve(check) :
  count = 0
  max_difficulty = 0
  min_difficulty = sys.maxsize

  for i in range(N) :
    compare = 1 << i
    if compare & check :
      count += questions[i]
      max_difficulty = max(max_difficulty, questions[i])
      min_difficulty = min(min_difficulty, questions[i])

      if count > R :
        return False
  
  if count < L :
    return False
  
  if max_difficulty - min_difficulty < X :
    return False

  return True


N, L, R, X = map(int, input().split(" "))

questions = []
questions = list(map(int, input().split(" ")))

check = (1 << N) - 1

count = 0
while check > 0 :
  if solve(check) :
    count += 1
  check -= 1

print(count)

어느 경우에 브루트포스하게 검사해야하는지, 다른 방법을 생각해야하는지 판단하는 것이 어렵다. 한 번 떠오른 풀이 방법을 다시 고민하는 것도... 이것도 내공의 문제인건가🤔 여러가지 문제를 더 풀어봐야할듯.

profile
어떻게든 굴러가고 있는

0개의 댓글