[python] 백준 18114 - 블랙 프라이데이
백준 18114 - 블랙 프라이데이 [GOLD5]
보통 세일은 대부분 이렇더라
골드5 문제치고는 정답률이 20%대입니다.
시간 제한은 국룰 2초가 아닌 1초인걸 보면, 시간 복잡도 낮추기가 관건인 문제인 것 같습니다.
문제의 특징은 다음과 같습니다.
최대 3개 내의 물품으로 무게 C를 맞춰야 합니다.
중복 없는 조합이며, 당연히 주어지는 무게는 모두 다릅니다.
가능한 조합 수가 아닌, 가능 여부를 출력합니다.
브루트 포스?
위의 1번과 3번 제약으로 인해, 당연히 모든 조합을 일일이 뒤져봐야 하는 거 아닌가? 하는 생각을 했습니다.
가능 여부는, 결국 모든 조합을 확인해야 불가능한지 파악이 가능하니까요!
또한 3개 고정이 아닌, 1개나 2개도 가능하기 때문에 더더욱 일일이 확인해야하는 줄 알았습니다.
물론, 브루트 포스 형식으로 구현하게 되면 시간복잡도는 N3이 됩니다.
N은 최대 5000이니, 대략 125억 정도입니다. 20분 정도 걸리겠네요.
다양한 방법으로 시간 복잡도를 줄이려 했으나, 어떻게 온몸을 비틀어도 절대 1초 안에 해결할 수는 없을 것 같았습니다.
저는 보통 30분 넘게 헤매면 문제 유형이라도 확인을 하는 편입니다.
문제 유형은…
??? 그 와중에 두 포인터 오타…
무려 네 개의 유형이 합쳐진 콤비네이션 유형!
브루트포스는 방금 완전탐색으로 시전을 했습니다.
완탐 온몸비틀기에서 정렬로 c보다 큰 값을 쳐내기도 했죠.
이분 탐색은 감이 잡히지만, 투 포인터는 어따 써먹을지 감도 안 잡혔습니다만,
역시 바람을 쐬고 오니 감이 잡힙니다.
이분탐색과 투 포인터의 조합
세 개를 구해야하는데, 투 포인터는 어디에 쓰는가?
투 포인터를 이분탐색의 top과 bottom으로 쓰면 해결되는 것입니다!
(left, right를 많이들 쓰지만, 저는 top/bottom을 선호하는 편입니다.)
문제 풀이 순서는 다음과 같습니다.
최대 3개 조합으로 무게 C를 맞춰야 합니다.
1-1. 변수명은 편의상 a, b, c로 하겠습니다.
1-2. 무게는 m으로 설정하겠습니다.
a는 arr[0], c는 arr[-1]로 시작합니다.
a + c = m이라면 답입니다.
a + c > m면 초과하면 c의 인덱스를 1씩 줄입니다.
a + c < m 미만이라면 b를 이분탐색으로 구합니다.
b를 이분탐색으로 구해도 답이 없다면, a의 인덱스를 전진시킵니다.
어떤 요소 x가 m과 같을 수 있으니, 시작 전에 검사합니다.
위의 순서에 따라 코드를 구현하면 됩니다.
한 개 값으로 C를 만족하는 경우는 7번에서 찾아집니다.
두 개 값으로 C를 만족하는 경우는 a와 c의 인덱스가 조절되며 자동으로 구해집니다.
세 개 값으로 C를 만족하는 경우는 이분탐색으로 b를 찾는 때에 구해집니다.
정답 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))
def bs(b, t, target):
while b <= t:
mid = (b+t) // 2
if arr[mid] > target:
t = mid - 1
elif arr[mid] < target:
b = mid + 1
else:
return 1
return 0
def two_point(i, j):
while i < j:
a, c = arr[i], arr[j]
# 2개 조합은 여기서 해결
if a + c == m:
return 1
elif a + c > m:
j -= 1
# 3개 조합은 여기서 해결
else:
b = m - (a + c)
# b가 a또는 c와 같을 수는 없다!
if b not in [a, c] and bs(i, j, b):
return 1
i += 1
return 0
i, j = 0, n-1
# 1개 조합은 여기서 해결
if m in arr:
print(1)
else:
print(two_point(i, j))
수고하셨습니다