eotlr720   5달 전

eclipse로 돌려보면 분명 답은 맞는것 같은데 제출하면 시간초과가 뜨네요ㅠㅠ

뭔가 더 효율적인 방법이 있을까 계속 고민해봤는데도 정말 답이 나오지 않아서 질문드립니다

어떻게 하면 시간초과를 없앨수 있을까요?

sksdong1   5달 전

다이나믹 프로그래밍으로 푸시면 됩니다.

힌트를 드리면

m일을 일할 때 가장 많은 이익을 얻어야 하므로, 무조건 m일을 일해야 됩니다. (음수가 없기 때문에 1~m-1일 사이에서는 최대가 나올 수 없죠)

따라서 1~m일 일한 값을 기준으로, m+1일을 더하고 1일 째를 빼고, m+2일을 더하고 2일 째를 빼면서 최대값을 비교하시면

O(n)에 해결 가능합니다.

eotlr720   5달 전

감사합니다! 한번 해볼게요!!

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