bubblepop   6년 전

만약 4개의 사탕의 정보가 다음과 같이 주어졌을때

4 8.00

1 1.00

3 2.00

5 4.00

6 3.00

가령 4원으로 만들수있는 경우는 1번 아이템 두개와 2번 아이템 한개를 구입해 총 5칼로리, 2번 아이템을 두개 구입해서 총 6칼로리 두개를 비교

해서 6칼로리를 저장하고있어야 한다고생각해서.

각동전을 k번 사용하는 경우를 계산하도록 알고리즘을 구현했는데 시간초과가 났습니다.

혹시나 해서

사탕 구입 갯수를 나타내는 k for문을 없애고 3중 반복문이아닌 2중 반복문으로 구하니까

AC를 받았습니다.

제가 처음에 생각했던 방식에 무슨 오류가 있던걸까요..



bubblepop   6년 전

아.. 점화식가지고 이것저것 표만들어보다 이유를 알게됬습니다. 

i번째 사탕을 구입하면 i-1번째 사탕의 칼로리 데이터를 이용하여 계산해야하는 0-1 knapsack 문제와 다르게 무한정 사탕을 살수 있기 때문에 

i번째 점화식 배열 f[j]를 채울 시점에는 i-1번째 사탕까지 고려해서 j원 투자해서 만들수있는 최대 칼로리가 저장되어 있고,   

i번째 사탕을 이용하는 경우에는 (j원 - i번째 사탕가격) + i번째 사탕 칼로리, 즉 i번째 사탕을 한개씩 추가했을 때 값과

i-1번째 사탕을 전혀 이용하지 않은 f[j] 값을 비교해서 큰 값으로 채워나가면,  

i번째 사탕이 사용된 경우 f(j - cost[i])원에 계속 누적되기 때문에 사탕의 구입 갯수를 나타내주는 변수 k를 위한 for문 한개를 제거 가능하네요.. 

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