13448번 - SW 역량 테스트
안녕하세요. 해당 문제를 풀어보다가 이해가 되지 않는 부분이 있어서 글을 남겨봅니다.
제 코드는 문제들을 시간 패널티(Pi -> tp)와 시간(Ri -> t)로 정렬하고(그리디한 접근을 위해), 소요되는 시간(T)를 용량으로 생각해서 각 용량에 들어갈 수 있는 최댓값들을 갱신하는 방식으로 풀어보았습니다.
그 결과 testcase.ac 사이트에서는 반례없이 잘 통과되고, 문제의 예시들도 문제없이 잘 동작하지만 1% 틀렸습니다가 나왔습니다. 이쯤되면 제 코드 알고리즘 자체에 문제가 있는것 같은데... 혹시 어떤부분에 문제가 있는지를 알려줄수 있으신가요?
그리고 정렬 자체에 문제가 있는지, dp 갱신방식에 문제가 있는지, 또 둘다 문제가 있는지도 궁금합니다.
댓글을 작성하려면 로그인해야 합니다.
thdtkfl5571 1년 전
안녕하세요. 해당 문제를 풀어보다가 이해가 되지 않는 부분이 있어서 글을 남겨봅니다.
제 코드는 문제들을 시간 패널티(Pi -> tp)와 시간(Ri -> t)로 정렬하고(그리디한 접근을 위해), 소요되는 시간(T)를 용량으로 생각해서 각 용량에 들어갈 수 있는 최댓값들을 갱신하는 방식으로 풀어보았습니다.
그 결과 testcase.ac 사이트에서는 반례없이 잘 통과되고, 문제의 예시들도 문제없이 잘 동작하지만 1% 틀렸습니다가 나왔습니다. 이쯤되면 제 코드 알고리즘 자체에 문제가 있는것 같은데... 혹시 어떤부분에 문제가 있는지를 알려줄수 있으신가요?
그리고 정렬 자체에 문제가 있는지, dp 갱신방식에 문제가 있는지, 또 둘다 문제가 있는지도 궁금합니다.