[백준] No.2515 - 전시장 (C++, DP)

문제

 

https://www.acmicpc.net/problem/2515

2515번: 전시장

 

풀이

 

solved.ac 난이도: Gold 2

 

 

높이 순서로 정렬 후, 해당 그림이 선택될 수 있도록 하는 앞의 그림들 중 가장 높은 그림을 미리 저장해 두자.

이를 저장하는 이유는 다음과 같은 점화식을 구현하기 위해서 이다.

 

dp[idx]를 idx번째 그림까지를 고려했을 때, 판매 가능한(선택된) 그림의 가격 합의 최대 값이라 고하자.

dp[idx]를 구할 때 두 가지 경우를 고려해 보아야 한다.

 

1. idx 번째 그림을 선택하지 않는 경우

idx번째 그림이 선택되지 않는다면 dp[idx]는 dp[idx-1] 값과 동일하다.

(dp[idx-1]의 값은 idx-1번째 그림까지 고려한 최댓값이다.)

 

2.  idx번째 그림을 선택하는 경우

idx번째 그림의 높이를 H라고 하자. 해당 그림을 선택하기 위해서는 그림 앞에 H - S 이하의 그림만 배치되어야 한다.

H - S 이하의 높이를 가지는 그림들 중 가장 높은 그림을 limit라고 하면 dp[idx]는 다음과 같다.

dp[idx] = dp[limit] + cost

 

따라서 dp[idx]는 1번(idx번째 그림은 건너뜀)과 2번(idx번째 그림을 선택)의 경우 중 더 큰 값이 된다.

dp[idx] = max( dp[idx-1], dp[limit] + cost )

 

 

이러한 구현을 위해서 limit[idx]에 idx번째 그림이 선택될 수 있도록 하는 앞의 그림들 중 가장 높은 것을 미리 저장하자.

 

for(int idx=1; idx<=picture_num ; ++idx){
  for(limit[idx] = limit[idx-1]; limit[idx] <idx ; ++limit[idx])
    if(pictures[idx].height - pictures[limit[idx]].height < S) 
      break;
  --limit[idx];
}

 

S의 값은 항상 모든 그림의 높이보다 작거나 같으므로

limit[idx-1]의 값에서 다음 그림들을 선택해보아 높이의 차가 S보다 작아지는 경우의 이전 그림이 limit[idx]의 값이 된다.

 

 

 

 

코드