4개의 댓글이 있습니다.
-
-
infoefficiency -
슬라이딩 윈도로 메모리를 줄이는 방법이 있지 않을까 생각해봅니다 ㅎㅎ 금액 같은 경우는 1000 원 단위이면 1000원을 1원으로 바꿔서 생각해도 될듯 싶습니다.ㅎㅎ 더 좋은 팁이 있다면 저도 궁금하네요
10년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
wjy721
안녕하세요
COINS을 풀다가 문득 궁금한 점이 있어서 질문 드립니다.
i번 이후의 동전들의 조합으로 금액 Sum을 만드는 Counting함수를 정의하고, 답을 구하는 과정에서 중복문제가 당연히 존재하므로 부분문제에 대한 답을 기억해두는 cache를 이용하여 문제를 풀었습니다.
해당 문제는 금액이 최대 5000, 동전의 종류가 최대 100개 이므로 cache메모리를 선언하는데 큰 문제가 없지만 만약 최대 금액이 몇 억 이상이라거나 동전의 종류가 굉장히 많은 경우에 cache메모리를 선언할 수 없게되는데 이런 경우에 어떤 방법으로 문제를 해결해야될지 잘 모르겠습니다.
다른 저지 사이트의 유사한 문제(링크)도 동적계획법으로 풀어야 될 것 같다는 생각은 들지만, 입력 크기가 너무 커서 곰곰히 생각해보다가 결국 포기하게 되었네요
이런 상황을 종종 마주치는데 문제 풀기가 매우 까다롭네요.
혹시 도움될만한 팁이나 노하우가 있으면 조언을 구하고 싶습니다.
감사합니다.
10년 전