Kick Start 2020#A Bundling

대충 재활훈련 (재활할 실력이 있었나 싶지만 ㅋㅋ) 힘내서 풀어보자 아자아자
Round A의 다른 세 문제는 블로그 어딘가 풀이를 올렸었다. 당시에 시간 내에 못 풀었던 Bundling만 풀어보자.

# Bundling
[문제]
N개의 문자열이 있고 K개의 그룹으로 나눴을 때 점수 합의 최댓값을 구하여라. 그룹의 점수는 문자열의 공통 Prefix의 길이이다.

[풀이]
그 안에 원소가 몇 개가 있든 상관없이 공통 Prefix가 많아야한다가 핵심이다. 트라이 만들고 가장 긴 원소를 기준으로 Prefix가 긴 것부터 K개씩 뽑아오면 된다.

[고찰]

• 대충 트라이 만들고 그리디하게 어찌저찌 하면 된다는 점은 눈치채기 쉽다. K개를 뽑아올 때, 가장 긴 거를 기준으로 K개를 뽑아오는게 이득일지, 아니면 가장 긴 K개를 가져올지 고민할 수 있는데 후자는 사실 전자에 포함된다. 구현 차이인데, 대부분의 트라이 구현에서 데이터는 연속되어 있어 차이가 없을 것이다.
• 위의 고민에 대한 결론을 내리고 나면 구현 어떻게 할 지도 나름 고민이 된다. 트라이야 뭐 옛날 코드 주워오면 되니 그렇다 쳐도 가장 긴 거를 기준으로 K개 뽑아오고, 다음 가장 긴 거를 어떻게 주워올까. 사실 이걸 고민한다는 건 트라이를 모르고 쓴다는 뜻이다 ^^ 이제 안다