1개의 댓글이 있습니다.
-
-
fleo0917 -
첫 번째 문제는 똑같은 문제가 알고스팟에도 있네요.
COINS
참고가 될런진 모르겠지만 제 답안 한 번 봐보세요.https://algospot.com/judge/submission/detail/311316
일반적인 dp입니다. 느린 건 탐색공간이 2차원이라서 그렇구요. 저는 반대로 여기서 상태공간을 1차원으로 줄일 방법을 몰라 한참 헤멨던 기억이 나네요. 똑같은 코드가 파이썬으로는 시간초과가 났거든요.
9년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
nosqeil24
안녕하세요,
저는 DP를 종만북으로 처음 접하였습니다.
종만북에서 소개하는 DP방식이 재귀적 DP였기 때문에
저는 재귀적DP로 대부분의 DP문제를 해결해왔습니다.
그런데 슬라이딩 윈도우 등 반복적 DP에서만 가능한 테크닉이 있기에
그런 테크닉을 쓰기위해서재귀적 DP로 푼 문제라도 다시 반복적 DP로도 풀어보려고 하고 있는데요,
지금까지 공부를 해오면서 반복적DP로 코드까지 짜서 정답 판정을 받은 코드 중에서
재귀적DP코드로 도저히 어떻게 짜야할지 감이 안오는 문제가 딱 2개가 있습니다.
첫번째 문제는 https://www.acmicpc.net/problem/2293 입 니다.
대부분의 정답코드는 1차원 다이나믹으로 반복적으로 해결했는데, 재귀적 DP로 어떻게 해야할지 모르겠습니다...
두번째 문제는https://www.acmicpc.net/problem/10982 입니다.
이 두 문제를 재귀적 dp로 어떻게 해결할 수 있나요?
타 사이트 문제라서 죄송합니다 종만북에서 배운 방식이라 여기에 질문을 올려야 될것같아서 질문드립니다. . 대부분 반복적DP를 쓰셔서
종만북에서 배운 재귀적 DP로도 풀 수 있는지 궁금합니다!
감사합니다
9년 전