[질문] [질문] 접근을 못하겠습니당..힌트좀 부탁드립니다ㅜ

[devbell..(devbelly)]

<문제>https://www.acmicpc.net/problem/17099

아에 접근도 못하겠습니다. 그리디인가용?? 동적계획법 태그 눌러서 들어왔는데 n이 너무 커서 당황스럽습니다.

힌트쫌만 주실수잇나요?? ㅜㅜㅜㅜ

[옥토끼(moonrabbit2)]

N^2 DP는 할수있음?

[devbelly(devbelly)]

네!

[옥토끼(moonrabbit2)]

DP테이블 채울때 i-1에서 고려한 j가 i에서도 반드시 고려할 수 있단걸 생각해봐

[devbelly(devbelly)]

감사합니다 형님!! 큐빙샤샤샥 풀고 다시 도전해볼게요

[devbelly(devbelly)]

감사합니다 ㅎㅎ 덕분에 풀었습니다. 얘는 탑다운은 사용불가능하죠?? 제가 바텀업은 거의 처음이라..

[옥토끼(moonrabbit2)]

탑다운으로 짜려고 하면 짤수는 있을꺼같은데 메리트는 없는거같음

[devbelly(devbelly)]

알겠습니다 ㅎㅎ 감사합니다!! - dc App

[익명(49.142)]

DP + 이분탐색, 대회를 1.끝나는 순, 2.시작 순으로 정렬하고, i 번째 대회와 겹치지 않는 대회 가장 큰 j ( j < i ) 를 찾아서 비교하면 됩니다.

[익명(121.184)]

i번째 대회의 시작시간을 기준으로 이전에 끝나는 대회들의 점수 중 최대를 찾아야 하는데 이 두 가지정보를 어떻게 동시에찾나요?

[익명(49.142)]

대회 j가 대회 i의 시작보다 일찍 끝난다면 dp[i] = max( dp[j] + 대회i 의점수 , dp[i-1]) 이런식으로 하시면 됩니다. dp[i] = max (대회i의 점수를 포함한 경우, 대회i의 점수를 포함하지 않은경우)

[익명(121.184)]

calculating.....

[익명(121.184)]

제가 지금 막힌곳이 j의 후보가 여러개가 될 수 있지 않나요? 그 중에서 최댓값을 가진 애를 찾아야되는데 그러면 선형시간이걸리는게아닌지....

[익명(49.142)]

dp[i]가 i번째 대회까지 치루고 받은 가장 큰 점수이기때문에 여러 j 후보 중 가장 마지막 j의 dp[j]에 이미 가장 큰 점수가 들어있습니다.

[익명(121.184)]

ㅇㅎ.....가릿 고수시네요

[devbelly(devbelly)]

감사합니다!!ㅎㅎ - dc App

[devbelly(devbelly)]

덕분에 풀었습니다 ㅎㅎ