수(기타) 놀이터

|

문제 코너

|

제출 현황

|

수학 Q/A

|

수학 quiz

|

koi_show 대회 풀이

 이 문제는 주어진 그림을 배치해 판매가능한 그림의 가격 합을 최대화하는 문제로 동적 계획법을 이용해 해결할 수 있다.

 일단 주어진 데이터를 높이를 기준으로 정렬한다. 

를 “ 를 마지막으로 골랐을 때 가장 좋은 값”으로 정의하자. 

그러면,  가 된다. 여기서  는 와 그림의 높이가  이상 차이가 나는 가장 큰 전시품의 번호이다.

 는 각 에 대해 를 구하여   에 계산할 수 있다. 그런데  가 커지면 는 항상 증가하므로 에 각각의 에 대해 를 미리 구할 수 있고,  그림까지의 답  를 와 동시에 구하면 에 답을 구할 수 있다. 

이를 위해서는 데이터를 높이 순서대로 정렬해야 하므로 총 시간 복잡도는  이 된다.