2156번 - 포도주 시식
실수로 질문을 지웠네요 -_-; 다시 올립니다.
왜 답이 나오지 않는지 모르겠습니다.
구한 방법은 입력을 다 받고,
i번째 까지의 포도주를 먹었을 경우 최대값을 dp[i]라고 할 때,
바로 그전 것을 먹는 경우와 점프해서 먹는 경우 중 최대값을 구해 i번째 포도주 값을 더해주었습니다.
그리고 동시에 dp[i]중 가장 최대값을 뽑아내게 하였습니다.
비슷한 문제로 보이는 계단 오르기(https://www.acmicpc.net/problem/2579)이와 유사한 방식으로 해결했는데...
무엇이 문제인가요?
위 점화식도 거의 모든 경우를 표현하는 것 같아서 반례찾는건 쉽지 않네요. ㅠㅠ
2차원 DP로 푸시면 좀더 쉬울꺼 같네요.
DP[i][j] = i번째 포도주에서 현재 연속으로 j개를 골랐을 때의 최대 비용
말씀하신 방법으로 다시 풀어서 Accept을 받긴 했지만...-_-; 모르는 부분에서 반례가 있긴 한가봅니다.
답변 감사합니다.
i번째 포도주를 안 먹은 경우가 더 좋을 때가 있기 때문입니다.
지금 dp식과 max구하는 곳 사이에 dp[i] = max(dp[i-1],dp[i]);를 추가하면 될 것 같네요.
dp[i] = max(dp[i-1],dp[i]);
댓글을 작성하려면 로그인해야 합니다.
chiller123 9년 전
실수로 질문을 지웠네요 -_-; 다시 올립니다.
왜 답이 나오지 않는지 모르겠습니다.
구한 방법은 입력을 다 받고,
i번째 까지의 포도주를 먹었을 경우 최대값을 dp[i]라고 할 때,
바로 그전 것을 먹는 경우와 점프해서 먹는 경우 중 최대값을 구해 i번째 포도주 값을 더해주었습니다.
그리고 동시에 dp[i]중 가장 최대값을 뽑아내게 하였습니다.
비슷한 문제로 보이는 계단 오르기(https://www.acmicpc.net/problem/2579)이와 유사한 방식으로 해결했는데...
무엇이 문제인가요?