https://www.acmicpc.net/problem/2515
시간 1초, 메모리 256MB
input :
- 그림의 개수 N (1<=N<=300,000)과 판매가능 그림을 정의하는 1이상의 정수 S가 입력.
- 그림의 높이와 가격 H, C(1 ≤ S ≤ H ≤ 20,000,000)(1 ≤ C ≤ 1,000)
output :
- 가격의 합이 최대가 되도록 배치했을 때 그 최대 합을 출력
조건 :
- 판매가능 그림 : 보이는 부분의 세로 길이가 특정 정수 S이상인 그림만 사게 된다고 가정한다.
도당체 어떻게 접근을 해야 하나 감이 잘 안 잡혔다.
다른 분들의 풀이를 봐도 어떻게 idx 앞에서의 최대 를 찾아야 하는지 잘 모르겠었었다.
높이에 대한 정렬을 통해서 어떤 것부터 앞에 세워야 할 지를 알아야 한다.
가장 중요한 것은 현재까지의 최댓값을 기록해두고 이 값에 현재 i 의 cost값을 더해 dp 값에 추가해주는 것이 필요했다.
그렇다면 최대 값을 구하기 전. 어떤 조건을 만족해야 판매 가능 그림이 되는지 다시 한 번 봐야 한다.
현재 i 번째 존재하는 그림의 높이가 아직 높이를 비교하지 않은 그림들 의 idx 들과 비교하여 S 이상의 차이가 나는 것이 있는지 확인.
그리고 이 idx의 dp값이 최대 값이 될 수 있는지를 확인 해야 한다.
for i in range(1, n):
while data[i][0] - data[idx][0] >= s and idx < i:
value = max(value, dp[idx])
idx += 1
dp[i] = value + data[i][1]i 0 1 2 3 4 5
8, 230 10, 100 15, 80 17, 200 20, 75 26, 80
idx 시작 0 0 2 2 3
idx 끝 0 2 2 3 5
최대값 0 0 230 230 310 430
dp 230 100 310 430 385 510위의 순서 대로 인덱스가 움직이고 가지고 있는 최대값이 업데이트 된다.
while 조건을 충족시키기 전까지는 계속 0을가지고 있어 자기 자신의 값만을 업데이트 하다가, 조건을 충족시키기 시작하면서 누적값을 가지게 된다.
그리고 dp값의 마지막 값을 찾는다 해서 언제나 큰 값일거라는 것은 확신할 수 없다. 차라리 그 앞의 것, 혹은 그 앞의 것만 전시하는 것이 더 높은 값을 얻을 수 있기 때문이다.
그래서 dp의 max값을 찾아 주어야 한다.
import sys
n, s = map(int, sys.stdin.readline().split())
data = []
dp = [0] * n
for i in range(n):
h, c = map(int, sys.stdin.readline().split())
data.append((h, c))
data.sort(key=lambda x:x[0])
dp[0] = data[0][1]
idx = 0
value = 0
for i in range(1, n):
while data[i][0] - data[idx][0] >= s and idx < i:
value = max(value, dp[idx])
idx += 1
dp[i] = value + data[i][1]
print(max(dp))어떻게 앞에서 최댓값을 기록하면서 갈지를 생각하면서 풀어야 하는 문제이다...
