yjs05   4달 전

SCPC 2016 2차 프리렌서문제 풀이법을 모르겠네요

저는 그리디하게

Q사를 선택하는것이 P사를 2주 선택하는것이 보다 이득일경우 Q사를 선택한다.
 2주연속 Q사가 이득일경우 3주중 2주동안 Q사를 선택하고 3주차에 P사를 하는것과
 1주에 P사를 2 3 주에 Q사를 수행하는것중 어떤것이 더이득인지 판별한다.

와같이 해결하려 했는데 결과는 0점이네요;;;;;

코드는 아래에 있는걸로 했습니다.

https://gist.github.com/juseongYun/5b9d44c85cae020... 

더 좋은 접근법이 있으면 알려주시면 감사하겠습니다.

sksdong1   4달 전

저는 DP로 풀었는데

문제가 정확히 기억은 안나는데

바탐업으로

dp(i)는 max(dp[i-1]+Q사의 이익, dp[i-2]+P사의 이익) 이런식?? 이였던거 같고

여기서 약간 조정 있긴 했던거 같은데 1~2줄 내로 풀렸던 걸로 기억하네요

yjs05   4달 전

그렇네요 최대값만 찾으면되니 그리디하게 할당하려고 고생할 필요는 없었네요
자세한 구현은 조금 고민해봐야겠습니다 ^^ 조언 감사합니다.

game2k   4달 전

maxPQ(i) = max(dp(p, i ), dp(q, i))

                   / max(dp(p, i - 1), dp(q, i -1)) + p(i)  (if k == p)
dp(k, i)  =  | 
                   \ max(dp(p, i - 2), dp(q, i -2)) + q(i)  (if k == q)

yjs05   4달 전

DP의 핵심코드를 적어주셨네요 ^^
덕분에 무엇을 잘못했었는지 확실히 알게되었습니다.
뉴비의 질문에 이렇게 관심가져주시는 회원님들 감사합니다.

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