이번 ACM 대전 two yachts문제관련 질문입니다. jeapi 대충 문제를 요약하자면 입력값에 첫 값은 요트빌리려는 사람의 수고(n<10000) 두번째 값 부터는 대여시작, 종료일, 가격 총 겹치는 구간은 100개 이하이다. 날짜는 최대 천만? 이었던 걸로 기억합니다. 다음과 같은 알고리즘으로 해결하면 문제가 되는 부분이 있을까요? 먼저 요트 하나로 구할 수 있는 최대 이득을 구합니다. 다음으로 먼저 구한 이득을 제외한 나머지 값 중 나머지 요트 하나로 구할 수 있는 최대 이득을 구합니다. 이렇게 풀게 되면 DP를 통해 O(nlogn)안에 풀리는 알고리즘이 아닌가 싶은데.. 반례가 있을까요? 9년 전
2개의 댓글이 있습니다. jeapi 하..방금 혼자서 반례를 찾앗네요 ㅠㅠ 안되는 알고리즘이네요..ㅎㅎ 9년 전 link VOCList 곰돌이디버깅 ㅠㅜ 9년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
jeapi
대충 문제를 요약하자면
입력값에 첫 값은 요트빌리려는 사람의 수고(n<10000)
두번째 값 부터는 대여시작, 종료일, 가격
총 겹치는 구간은 100개 이하이다.
날짜는 최대 천만? 이었던 걸로 기억합니다.
다음과 같은 알고리즘으로 해결하면 문제가 되는 부분이 있을까요?
먼저 요트 하나로 구할 수 있는 최대 이득을 구합니다.
다음으로 먼저 구한 이득을 제외한 나머지 값 중 나머지 요트 하나로 구할 수 있는 최대 이득을 구합니다.
이렇게 풀게 되면 DP를 통해 O(nlogn)안에 풀리는 알고리즘이 아닌가 싶은데.. 반례가 있을까요?
9년 전