chiller123   9년 전

실수로 질문을 지웠네요 -_-; 다시 올립니다.

왜 답이 나오지 않는지 모르겠습니다.

구한 방법은 입력을 다 받고,

i번째 까지의 포도주를 먹었을 경우 최대값을 dp[i]라고 할 때,

바로 그전 것을 먹는 경우와 점프해서 먹는 경우 중 최대값을 구해 i번째 포도주 값을 더해주었습니다.

그리고 동시에 dp[i]중 가장 최대값을 뽑아내게 하였습니다.

비슷한 문제로 보이는 계단 오르기(https://www.acmicpc.net/problem/2579)이와 유사한 방식으로 해결했는데... 

무엇이 문제인가요?

pl0892029   9년 전

위 점화식도 거의 모든 경우를 표현하는 것 같아서 반례찾는건 쉽지 않네요. ㅠㅠ

2차원 DP로 푸시면 좀더 쉬울꺼 같네요.

DP[i][j] = i번째 포도주에서 현재 연속으로 j개를 골랐을 때의 최대 비용

chiller123   9년 전

말씀하신 방법으로 다시 풀어서 Accept을 받긴 했지만...-_-; 모르는 부분에서 반례가 있긴 한가봅니다.

답변 감사합니다.

baekjoon   9년 전

i번째 포도주를 안 먹은 경우가 더 좋을 때가 있기 때문입니다.

지금 dp식과 max구하는 곳 사이에 dp[i] = max(dp[i-1],dp[i]);를 추가하면 될 것 같네요.

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