전시장

🤔 접근

• 처음에는 냅색문제와 비슷한 풀이 방법을 생각해보았다.
  각 높이 별로 dp 테이블을 생성하고 dp를 돌면서 해당 높이의 그림을 추가하며 dp를 갱신하는 방식을 생각했다.

  dp = [0] * max(heights)

• 그런데, 그림이 존재하지 않는 공간에 대해서는 dp가 불필요하다고 느껴졌다.
• 결국, 그림을 추가하는 시점에 데이터가 업데이트 되기 때문이다.
  그래서 dp 테이블을 따로 생성하지 않고 prices 라는 딕셔너리 자료형을 사용하였다.
  key 값으로 그림의 높이를 받고, value값으로는 가치를 저장하였다.

딕셔너리 자료형을 이용하여 존재하는 그림의 높이에 대해서만 value값을 저장할 수 있었다.

해당 높이 l 까지의 최대 가치를 구하기 위해서는 높이가 l-s 이하인 그림 중 가장 큰 그림의 높이를 찾는 것이 핵심이었다.

## heights = [그림들의 높이 저장]

for i, l in enumerate(heights): 
    # l-s 이하 중 가장 큰 그림을 찾는게 핵심
    if i == 0:
        continue
    prices[l] = max(prices[heights[i-1]], find_p(l-s) + prices[l])

그럼 결국 heights 를 정렬시키고 l-s보다 작은 그림 중 가장 큰 그림을 찾는 이분탐색 문제가 된다.

def find_p(x): # 높이가 x 보다 작거나 같은 그림 중 가장 큰 그림의 가격을 찾아라
    start = 0
    end = len(heights)
    res = 0
    while start<=end:
        mid = (start + end) // 2
        if heights[mid] <= x:
            res = prices[heights[mid]]
            start = mid + 1
        else:
            end = mid - 1
        
    return res

💻 전체 코드

# 2515
import sys
input = sys.stdin.readline

n, s = map(int, input().split())
heights = []
prices = {}
for _ in range(n):
    h, p = map(int, input().split())
    if h < s:
        continue
    if h in prices:
        prices[h] = max(prices[h], p)
    else:
        prices[h] = p
        heights.append(h)

heights.sort()

def find_p(x): # 높이가 x 보다 작거나 같은 그림 중 가장 큰 그림의 가격을 찾아라
    start = 0
    end = len(heights)
    res = 0
    while start<=end:
        mid = (start + end) // 2
        if heights[mid] <= x:
            res = prices[heights[mid]]
            start = mid + 1
        else:
            end = mid - 1
        
    return res


for i, l in enumerate(heights): 
    # l-s 이하 중 가장 큰 그림을 찾는게 핵심
    if i == 0:
        continue
    prices[l] = max(prices[heights[i-1]], find_p(l-s) + prices[l])

print(prices[l])