his130   1년 전

처음에 2차원 배열로 캐시값을 구현했더니, 메모리 초과가 나서,

낭비되는 공간이 많은 것 같아서 DP 를 map 을 써서 구현했습니다.

map 은 이진 탐색 트리라 탐색속도가 빠른 것 같은데 어느 부분에서 시간초과가 나는 걸까요?


점화식은 D[K][F] = K를 만드는 경우의 수 (F는 사용한 가장 큰 동전의 인덱스)

동전은 coin 변수에 가장 큰 값부터 역순으로 저장을 해놨습니다.

그래서 본문 예제처럼 K 가 10이고, 동전의 갯수는 3개 1 ,2, 5 일때

coin[0]=5,coin[1]=2,coin[2]=1 이 되고

구하고자 하는 D[10][0] 은 

D[5][0] , D[5][1] , D[5][2] 이런식으로 분할됩니다.

D[5][0] 는 5 5 , 5 2 2 1 , 5 2 1 1 1 , 5 1 1 1 1 1 이런값이 들어가고

D[5][1] 에는 2 2 2 2 2 , 2 2 2 2 1 1 , 2 2 2 1 1 1 1, 2 2 1 1 1 1 1 1 , 2 1 1 1 1 1 1 1 1

D[5][2] 에는 1 1 1 1 1 1 1 1 1 1 

이런식으로 들어가는 점화식입니다.

72%정도가서 시간초과 에러가 뜨는데... 어떤 문제인지 궁금합니다.

map 이 배열보다 속도가 느린건 알지만...

이래서 DP 에서 map 을 안 쓰는건가요??


추가적으로... 이게 안된다면 이 문제는 재귀적으로 풀 방법이 없나요..?

아무리 뒤져도 재귀로 푸신분들은 안보이고..

풀려면 이차원으로 풀어야 할 것같은데..메모리초과가 나고...ㅠㅠ

201313987   1년 전

n 제한은 10,000이 아니라 100이라 메모리에 문제는 없을 것 같습니다.

map이 많이 느리기도 하구요

his130   1년 전

map의 문제군요.. ㅠㅠ

감사합니다!

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