계속 틀리는데 아예 잘못 접근한건지 아니면 사소한 실수가 있는건지 잘 모르겠네요....
검색해봤다가 저도 모르게 풀이까지 보게 될 것 같아서 부탁드립니다.
문제는 https://www.acmicpc.net/problem/13448 이거입니다.
풀이 : 풀 문제의 조합이 정해지면(예를 들어서 1, 2, 3, 4, 5 다섯 문제가 있다고 할 때, 1, 3, 5번을 푸는 게 최적이라는 것이 정해지면)항상 시간에 따라 감소하는 점수가 큰 것부터 푸는 것이 최적일 것이다. 따라서 문제들을 시간에 따라서 감소하는 점수가 큰것을 기준으로 내림차순 정렬을 하고, 앞에서부터 Knapsack DP를 푸는 것처럼 해당 문제를 조합에 넣었을 때와 안 넣었을 때를 비교하면서 최적의 조합을 찾는다.
풀이 코드는 아래와 같습니다.
Ri가 큰 게 앞에 있으면 그거 푸느라 다른 거 푸는 시간이 뒤로 많이 지연되어서 점수가 떨어질 듯 Ri도 잘 고려해봐
이거 제가 이해를 못해서 진짜 죄송한데 혹시 예시 하나만 들어주실 수 있나요?? 제가 뭔가 잘못 생각하고 있는 거 같은데...
아 깨달았어요 맞네요 ㅠㅠ
이러니까 감이 안와버리네요....
앗 혹시 풀고 남은 시간이랑 감소하는 시간이랑 곱하는건가