Kick Start Round A 2020 후기

얍! 후기 써야지

네 문제 다 전형적인 느낌이다.

코딩할 줄 알고 (Allocation) / DP (Plates) / 파라메트릭 서치 (Workout) / 트라이 (Bundling) 를 다루어봤다면 쉽게 풀이를 떠올릴 수 있다. 그렇지만 트라이를 살면서 한 번 짜봐서 4번이 나한테는 까다로웠을 것 같다. 3번까지 빠르게 풀어서 올솔할 수도 있었을 것 같은데, 중간에 잠들어서 결국 3솔했다

 

 

 

---

# Allocation

 

[문제]

N개의 집이 있고, 각각의 가격은 다르다. B달러가 있으면, 집을 최대 몇 개 살 수 있을까?

 

[풀이]

쉬운 그리디이다. 가격 순으로 정렬하고, 싼 것부터 사면 된다.

---

# Plates

 

[문제]

N개의 묶음이 있고, 각 묶음에는 K개의 접시가 있다. ( 접시의 Beauty가 NxK 행렬로 주어진다. )

각 묶음에서는 위에서부터 접시를 선택할 수 있다고 할 때, P개의 접시를 골랐을 때 Beauty의 합의 최댓값은 얼마인가.

 

[풀이]

누적합 만들어두고, DP하면 된다.

DP 순서 살짝 헷갈렸는데 나는 다음과 같이 구현했다.

for(int i=2;i<=N;i++){
    for(int j=1500;j>=0;j--)
        if(dp[i-1][j]!=-1){
            for(int k=0;k<=K&&j+k<=P;k++)
                dp[i][j+k]=max(dp[i][j+k], dp[i-1][j]+dish[i][k]);

---

# Workout

 

[문제]

N개의 시각이 주어지는데, 여기에 K개의 시각을 추가해서, 각 시각간의 간격의 최댓값을 최소화하는 문제이다.

 

[풀이]

그냥 최소화하기는 까다로워보이므로, Parametric Search를 떠올릴 수 있다.

간격의 최댓값 범위(log T)에 대고  각 케이스마다 O(N)에 true/false를 판단하며 Parametric Search를 하면 된다.

---

Bundling은 못 풀었으니까 안 써야지 ㅎ

친구피셜 트라이하고, 깊이가 깊은 것부터 빼면 된다고 한다.