동전과 급여라고 하는 두 개의 양수 목록이 있다고 가정합니다. 여기서 코인[i]은 코인 i의 가치를 나타내고, 급여[j]는 근로자 j에게 지불해야 하는 최소 급여 금액을 나타냅니다. 이제 유형당 하나의 동전이 있고 각 작업자에게 정확히 하나의 동전을 주어야 한다고 가정하고 각 작업자에게 동전을 주는 방법의 수를 계산해야 합니다. 여기서 어떤 작업자가 한 가지 방법으로 한 가지 유형의 동전을 받고 다른 방법으로 다른 유형의 동전을 받는 경우 두 가지 방법이 다릅니다. 결과가 매우 크면 결과 모드 10^9+7을 반환합니다.
따라서 입력이 동전 =[1, 2, 3], 급여 =[1, 2]인 경우 출력은 4가 됩니다. 마치 첫 번째 동전(값 1)을 사용하지 않는 것처럼 두 동전 모두 두 근로자 모두에게 유효하므로 두 가지 방법으로 근로자에게 급여를 지급할 수 있습니다. 이제 첫 번째 코인을 사용하면 첫 번째 작업자에게만 갈 수 있으며 나머지 동전 중 하나를 사용하여 두 번째 작업자에게 지불할 수 있습니다. 네 가지 방법이 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 목록 코인 정렬 및 목록 급여 정렬
- num_coins :=동전 크기
- num_salaries :=급여 규모
- dp :=새 지도
- 급여의 각 급여에 대해 다음을 수행합니다.
- l :=0, r :=num_coins - 1
- idx :=num_coins
- l <=r인 동안, do
- m :=l +(r - l) / 2
- 동전[m]>=급여인 경우
- idx :=m
- r :=m - 1
- 그렇지 않으면
- l :=m + 1
- idx가 num_coins와 같으면
- 0을 반환
- dp[급여] :=idx
- res :=1
- num_salaries - 1에서 0 사이의 i에 대해 1 감소, do
- 급여 :=급여[i]
- idx :=dp[급여]
- res :=res *(num_coins - idx + 1) -(num_salaries - i)
- Return res mod 10^9+7
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution:
def solve(self, coins, salaries):
coins.sort()
salaries.sort()
num_coins = len(coins)
num_salaries = len(salaries)
dp = {}
for salary in salaries:
l = 0
r = num_coins - 1
idx = num_coins
while l <= r:
m = l + (r - l) // 2
if coins[m] >= salary:
idx = m
r = m - 1
else:
l = m + 1
if idx == num_coins:
return 0
dp[salary] = idx
res = 1
for i in range(num_salaries - 1, -1, -1):
salary = salaries[i]
idx = dp[salary]
res *= (num_coins - idx + 1) - (num_salaries - i)
return res % (10**9+7)
ob = Solution()
coins = [1, 2, 3]
salaries = [1, 2]
print(ob.solve(coins, salaries)) 입력
[1, 2, 3],[1, 2]
출력
4