kkw564   4년 전

지수적 DP를 생성하여 MAP을 이용하여 제작하였는데 어느 부분에서 틀린지 잘 모르겠네요 ㅠㅠ

cout부분 주석을 제거하면 어떻게 작동하는지 알 수 있습니다 ㅠㅠ!

cprayer   4년 전

해당 부분을 왜 저렇게 작성했는지 모르겠습니다

반례입니다.

20 2 2


32

kkw564   4년 전

제가 생각했을 때는 DP값의 고정이 다음과 같이 된다고 생각했습니다.

예를들어 1000000 500 600일 경우
DP[0] :: 1
DP[1~499] :: 2
DP[500~599] :: 3
DP[600~249999] :: 4
DP[250000~359999] :: 5
DP[360000~끝] :: 6
이라고 생각하여 풀어서 다음과같이 코드를 작성하였는데

이렇게 생각한 DP값이 틀린건가요??

kkw564   4년 전

반례를 통해 제 코드가 틀렸음은 이해가 되지만 그 뒤로 어떻게 손을 봐야할지 잘 감이안오네요ㅠ

cprayer   4년 전

정의를 그대로 이용하시는게 낫습니다.  즉 함수의 인자로 i가 들어왔을 때
m[i]가 매핑되어 있지 않다면 m[i / p], m[i / q]를 인자로 재귀호출하고 리턴된 값을 토대로 매핑하시면 됩니다.

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