프로그래머스. 거스름돈

https://programmers.co.kr/learn/courses/30/lessons/12907

코딩테스트 연습 - 거스름돈

 

연습문제고 푼 사람도 2000명대여서 금방 풀줄 알았는데 생각보다 너무 어려웠던 문제다.

간단한 dp로 풀릴줄 알았는데 아니였다...

 

처음에는 d[n] 배열을 만들어서 d[n-동전액수]를 더해가면 될줄 알았다.

예를들어 5원을 [1,2,5]원으로 거슬러 줄 수 있는 방법은 d[5-1] = d[4]의 경우에서 1원을 추가해주는 경우 +

d[5-2] = d[3]에서 2원을 추가해주는 경우 + d[5-5] = d[0]의 경우에서 5원을 추가해 주는 경우 

이런식으로 생각했는데 문제가 있었다.

위 방법으로 하면 중복되는 경우가 생긴다는 것이다.

예를들어 5원을 만드는 경우가 d[2]에서 3원을 더하는 경우, 

d[3]에서 2원을 더하는 경우가 같이 더해지는데 사실 이 둘은 같은 경우라서 중복된다.

 

결국 방법을 찾아봤는데 답은

1원으로 만드는 경우

1원,2원으로 만드는 경우

1원,2원,5원으로 만드는 경우 

이런식으로 경우를 나누는 것이였다.

점화식은 d[i][j] += d[i][j-coin]

 

시간초과 코드:

 

그런데 이 코드는 효율성에서 시간초과가 났다.

솔직히 시간초과의 이유를 모르겠다.

n의 최대 값 100000, 동전 종류의 최댓값 100이므로 O(100000*100) = O(천만)으로 이 코드도 충분히 빠르다고 생각하는데..

추측하는건 d[i][j] += d[i-1][j] % MOD 처럼 윗행의 값을 더해주는 연산이 한번더 있어서 그런건가 싶다.

하지만 내가 알기로 array access는 항상 상수시간이 걸리는 걸로 알고 있는데 아무리 봐도 모르겠다.

혹은 그냥 문제 자체가 제한시간이 엄청 빡빡한걸수도 있다.

 

통과한 코드: