예를 들어 9999원짜리가 있고 2원짜리 동전만 100개 있다고 칩시다. (실제로 이런 데이터는 조건이 안맞겠지만...)
위쪽 코드는 memo[1] =10000000 인 값을 유지해서 func(1)에 대한 메모이제이션이 제대로 동작되지 않고 10000번 호출되게 됩니다.
아래쪽 코드는 mic(1)을 호출하면 그 값을 -1에서 0x3f3f... 으로 변경하기 때문에 두번째로 호출되는 mic (1)에서는 for문을 돌지 않게 됩니다.
결국 방법의 문제가 아니라, 메모이제이션이 제대로 안되서 생기는 문제였습니다.
ljk0411jg 7년 전
위에 소스는 시간 초과가 난 소스이고 아래 소스는 ac받은 소스입니다.
두 소스다 k부터 0까지 내려오는 소스이고 캐시 배열에다 그 번호를 만들수 있는 동전 갯수 들의 최솟값을 저장하는 방식입니다. 위에소스는 for문 안에 조건을 주었고 아래소스는 for문 밖에 조건을 주었습니다. 같은 방식인데 위에 소스는 왜 시간 초과 나는지 궁금합니다.