처음에는 무슨 문제인지조차 이해 못했다.
내가 알던 냅색 문제랑 좀 다른 거 같기도 하고..
찬찬히 읽어보니, 무게 제한만 넘기지 않으면 각 물건들에 대해 가방에 들어가거나 안 들어가거나 두 개의 선택이 있다.
처음에는 별 생각없이 dfs로 접근했다.
모든 물건마다 넣고, 않 넣고에 따라 깊이 탐색하는 방식으로.
제출해보니 시간초과.
곰곰이 생각해보니 물건 30개면 최대 2^30 번의 연산이 필요해진다.
감이 잡히지 않아서 구글의 힘을 빌렸다.
투 포인터 문제란다. 그리고 물건을 두 개의 그룹으로 나눠야한다 카더라.
30개의 물건 조합 = 2^30
15개의 물건 조합 = 2^15. 그룹이 2개니까 이걸 두 번하면 2^16
획기적으로 줄어든다.
두 그룹으로 나눠서 연산하고 두 번째 그룹은 정렬을 했다. 그럼 무게 제한보다 커지면 바로 break 할 수 있어지니까!
나름 머리써서 짠 코드다.
num_stuff, limit = map(int, input().split())
stuff_list = sorted(list(map(int, input().split())))
answer = 0
first = []
second = []
def check_and_put(index, end, weight):
global limit
global num_stuff
if end == num_stuff:
if index == end:
second.append(weight)
return
if weight <= limit:
check_and_put(index+1, end, weight)
else:
return
if stuff_list[index] + weight <= limit:
check_and_put(index+1, end, stuff_list[index] + weight)
else:
return
else:
if index == end:
first.append(weight)
return
if weight <= limit:
check_and_put(index+1, end, weight)
else:
return
if stuff_list[index] + weight <= limit:
check_and_put(index+1, end, stuff_list[index] + weight)
else:
return
check_and_put(0, num_stuff // 2, 0)
check_and_put(num_stuff // 2, num_stuff, 0)
second.sort()
answer = 0
for num1 in first:
for num2 in second:
if num1 + num2 > limit:
break
answer += 1
print(answer)보기 좋게 시간초과. 왜지?
맞다, 투 포인터!
그런데 어떻게 쓸지 감이 안 잡혔다.
음, 아무리 생각해봐도 그냥 2중 반복문밖에 안 나올텐데...
투 포인터라는 힌트를 갖고 일단 두 그룹에 모두 정렬하는 방식으로 바꿨다.
그리고 알았다!
나 스스로가 너무 멍청하다고 느껴졌다.
당연한건데 이걸 왜...
첫 번째 그룹의 포인터 i는 0부터 증가.
두 번째 그룹의 포인터 j는 뒤부터 감소.
(각 포인터가 가리키는 값의 합 <= 무게제한)이 되는 순간의 j+1값을 정답 값에 더해주면 된다.
그리고 i가 1 증가된 다음 iteration에서도 j는 이전 iteration의 자리부터 시작하면 된다...
num_stuff, limit = map(int, input().split())
stuff_list = sorted(list(map(int, input().split())))
answer = 0
first = []
second = []
def check_and_put(index, end, weight, half_list):
global limit
global num_stuff
if index == end:
half_list.append(weight)
return
if weight <= limit:
check_and_put(index+1, end, weight, half_list)
else:
return
if stuff_list[index] + weight <= limit:
check_and_put(index+1, end, stuff_list[index] + weight, half_list)
else:
return
check_and_put(0, num_stuff // 2, 0, first)
check_and_put(num_stuff // 2, num_stuff, 0, second)
first.sort()
second.sort()
answer = 0
p2 = len(second) - 1
for num1 in first:
while p2 > -1:
if num1 + second[p2] > limit:
p2 -= 1
else:
answer += p2 + 1
break
print(answer)얏호 정답!
참 초보자스러웠다...
