thdtkfl5571   1년 전

안녕하세요. 해당 문제를 풀어보다가 이해가 되지 않는 부분이 있어서 글을 남겨봅니다.

제 코드는 문제들을 시간 패널티(Pi -> tp)와 시간(Ri -> t)로 정렬하고(그리디한 접근을 위해), 소요되는 시간(T)를 용량으로 생각해서 각 용량에 들어갈 수 있는 최댓값들을 갱신하는 방식으로 풀어보았습니다.

그 결과 testcase.ac 사이트에서는 반례없이 잘 통과되고, 문제의 예시들도 문제없이 잘 동작하지만 1% 틀렸습니다가 나왔습니다. 이쯤되면 제 코드 알고리즘 자체에 문제가 있는것 같은데... 혹시 어떤부분에 문제가 있는지를 알려줄수 있으신가요?

그리고 정렬 자체에 문제가 있는지, dp 갱신방식에 문제가 있는지, 또 둘다 문제가 있는지도 궁금합니다.

doju   1년 전

아쉽지만 두 부분 모두에 문제가 있어 보입니다. 반례는 후자(DP 갱신 방식)에 대해서만 드립니다.

댓글을 작성하려면 로그인해야 합니다.