price[i]가 상점에서 i번째 항목의 가격을 나타내는 price라는 배열이 있다고 가정합니다. 특별 제안이 진행 중입니다. i 번째 항목을 구매하면 price[j]에 해당하는 할인을 받게 됩니다. 여기서 j는 j> i이고 j번째 항목의 가격은 i번째 항목(예:가격[j] <=가격[i]), 그렇지 않으면 할인을 전혀 받지 않습니다. i번째 요소가 특별 할인을 고려하여 상점의 i번째 항목에 대해 지불할 최종 가격인 배열을 찾아야 합니다.
따라서 입력이 가격 =[16,8,12,4,6]과 같으면 item0의 가격이 16이므로 출력은 [8, 4, 8, 4, 6]이 됩니다. price[1]=8에 해당하는 할인, 그러면 최종 가격은 8 - 4 =4가 됩니다. item1에 대해 price[1]이 8인 경우 price[3]=2에 해당하는 할인을 받게 되므로 최종 가격은 우리가 지불할 가격은 8 - 4 =4입니다. price[2]가 12인 항목 2의 경우 가격[3] =4와 동일한 할인 값을 얻습니다. 따라서 지불할 최종 가격은 12 - 4 =8. 3번과 4번 항목은 할인을 받지 않습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
범위 0에서 가격 크기까지의 i에 대해
-
i+1 범위의 j에 대해 가격 크기까지
-
가격[i]>=가격[j]이면
-
가격[i] :=가격[i] - 가격[j]
-
루프에서 나오다
-
-
그렇지 않으면
-
j :=j + 1
-
-
-
-
반품 가격
예제(파이썬)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(prices): for i in range(len(prices)): for j in range(i+1,len(prices)): if(prices[i]>=prices[j]): prices[i]-=prices[j] break else: j+=1 return prices prices = [16,8,12,4,6] print(solve(prices))
입력
[16,8,12,4,6]
출력
[8, 4, 8, 4, 6]