Google Kick Start(Round A 2020)

1. Allocation

오름차순으로 정렬한 뒤 돈이 부족할때 까지 산다.

 

- 시간 복잡도

sorting part : O(NlogN) => Counting sort로 O(N)으로 단축 시킬 수 있음

processing part: O(N)

=> 총 O(N)

2. Plates

Dynamic programming 이용

첫 N stack에서 P개를 뽑아 만들수 있는 maximum sum을 dp[N][P]라고 하면

dp[i][j] = max(dp[i][j],sum[i][x]+dp[i-1][j-x])

 

for i [1,N]:

  for j [0,P]:

    dp[i][j] =0

    for x [0,min(j,K]:

       dp[i][j] = max (dp[i][j],sum[i][x]+dp[i-1][j-x])

 

- 시간 복잡도

O(N*P*K)

3. Workout

initial difference: di

maximum difference after inserting: dopt

trainning need to insert between the difference to make optimal: ceiling(di/dopt)-1 => ki

ksum = k1+k2+...+k(n-1) < K

 

1<dopt<max(di)

 

binary search로 dopt를 찾음

 

- 시간 복잡도

processing part: O(N) => 하나씩 돌면서 나누기

max(di)<10^9 이므로

O(log(10^9)*N)

 

4. Bundling

각 prefix의 기여도의 합산을 높이는게 목적

Pi: prefix of S strings