0zero0   7달 전

현재 매 차례에서 모든 나무에 대해서 그 나무를 자를 때의 이득(코드에서의 benefit)을

(만들 수 있는 울타리의 길이)+(둘레의 감소량)으로 계산하여 매번 가장 benefit이 큰 나무를 자르다가 (Greedy)

만약 benefit이 같은 것들이 나온다면 이제 n개 중에서 cnt개를 골라 잘랐을 때 현재 만들 수 있는 울타리의 길이가 둘레 이상이 되는 경우가 생길때까지 cnt를 키워주는 방식의 BruteForce 방식으로 구해주는 알고리즘을 생각하였습니다.

혹시 반례가 찾아주실 수 있을까요? (2%에서 틀렸습니다가 나옵니다)

또한 제 생각에서 그리디에서 브루트포스로 전환되는 지점에 따라 결국 worst complexity는 브루트포스를 따르게 됨으로 브루트포스만을 돌려서 결과를 보려고 하였지만 그런 경우에는 메모리초과가 발생하네요 ㅠㅠ 혹시 이건 제가 파이썬으로 코딩해서 그런걸까요? c++로 그냥 브루트포스를 돌리면 통과할 수도 있을까요,,,

원래 차근차근 단계에 맞게 풀다가 이 문제를 발견해서 풀 수 있을 것 같아서 도전하고 있는데 몇일째 해결을 못하고 있어서 이렇게 도움을 부탁드립니다. 감사합니다.

혹시 주석이 빈약하면 수정해서 글 다시 올리도록 하겠습니다!

0zero0   7달 전

혹시 제가 그리디에서 이득값을 잘못 설정하고 있는 것일까요,,? ㅠㅠ 뭔가 특정 상황에 대해서 고려를 못하고 있는 느낌인데 너무 찾기가 힘드네요,,,

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