2790 타이어 팔기 (정올, python3)

https://jungol.co.kr/problem/2790

시간 제한	메모리 제한
1초	64MB

문제

병호가 ‘L’백화점에서 ‘N’타이어를 팔려고 한다. 공장에서 출고한 타이어는 총 N종류 있다. 허나, 타이어들의 부피가 너무 크기 때문에 타이어를 운송할 때 타이어 안에 타이어를 끼우는 식으로 운송해야 한다.

병호가 ‘L’백화점에서 ‘N’타이어를 팔려고 한다. 공장에서 출고한 타이어는 총 N종류 있다. 허나, 타이어들의 부피가 너무 크기 때문에 타이어를 운송할 때 타이어 안에 타이어를 끼우는 식으로 운송해야 한다.

 

입력

첫 번째 줄에는 출고한 타이어의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 

두 번째 줄부터 N개의 줄에는 각 타이어의 안지름 I, 바깥지름 O, 가격 P가 주어진다.

1 ≤ I < O ≤ 1,000,000,000, 1 ≤ P ≤ 1,000 전체 데이터의 50%는 1 ≤ N ≤ 1,500이다.

 

출력

병호가 팔 수 있는 타이어의 가격의 합의 최댓값을 출력한다.

 

---

풀이

 

2584 전시장 (정올, python3)

이 문제에 좌표압축 섞어서 해결할 수 있습니다.

 

타이어 내경과 외경을 모두 포함한 직경 데이터를 좌표압축해서 0부터 최대 99,999까지의 데이터로 만듭니다. 이걸 가지고 세그먼트 트리를 만들 수 있습니다. 직경 `di`에 대해 `di`내에 채울 수 있는 타이어의 최대 가치를 `seg[di]`로 처리합시다.

 

타이어 정보를 외경을 기준으로 오름차순 정렬합니다. 순서대로 타이어를 확인하면, 내경보다 작은 외경을 가진 타이어는 모두 확인했으므로 `seg[inner_di]`는 가능한 모든 타이어를 확인한 상태로 정리되어있습니다. 즉, 이번에도 최댓값 세그먼트 트리를 활용해 현재 타이어의 내경 이하의 최적해에 현재 타이어의 가치를 더한 것을 `seg[outer_di]`에 저장하고 갱신합니다. 단, 이때 이미 들어있는 값이 현재 탐색한 값보다 크다면 갱신하지 않습니다.

 

 

 

정답 코드

좌표압축 전처리가 더 복잡하네요.

for i, o, p in tire:
    t = query(i)+p
    if seg[size+o] < t:
        update(o, t)
print(seg[1])