meme0724   1년 전

앞에 올린거랑 이어서 이것도 시간초과가 뜨네요;;

n원을 만들려고 하고 그 방법이 f(n)가지라고 할때

동전의 종류가 k1, k2....kn개가 있으면

f(n-k1), f(n-k2),... 등을 먼저 구해서 f(n)의 최솟값을 구하는 방식으로 했는데

이것도 시간을 많이 잡아먹나 보네요...

ㅅ시간 안에 풀 수 있는 방법좀 가르쳐 주시면 감사하겠습니다!!

movie_jo   1년 전

만능링크

링크에 있는 피보나치 예제랑 비슷하게

f(n)을 구할 때 그 아래에 있는 이미 구한 f(n-k)들이 중복이 많아서 시간초과가 날거에요

그래서 한번 계산한 f(x)를 저장해놓고 불러내는 방식이 링크에 나옵니다!

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