Editorial

---

1801C

summary:

앨범 $n$개가 있고, 앨범 하나당 $m$개의 트랙이 있다. 각 트랙은 cool 수치를 가진다.

음악을 들을 때 이전에 들은 모든 음악보다 cool수치가 높으면 만족도가 1 오른다.

모든 앨범을 들었을 때 최대 만족도를 구하는 문제이다. 음악은 트랙 단위로 들을 수 없고, 앨범 단위로 들을 수 있다.

solution:

일단 앨범의 모든 트랙이 증가하는 coolness를 가지도록 압축시킨다. 어차피 이전에 들었던 최대 coolness만 만족도에 영향을 주기 때문이다. ex) [1,4,2,3,6,5,9] => [1,4,6,9]

그리고 모든 coolness 수치마다 그 트랙이 포함된 앨범 번호를 저장한다.

그 다음 coolness 수치를 오름차순으로 탐색하는데, $d_i$: i앨범을 들었을 때 (현재 coolness까지) 최대 만족도라고 정의하고, 현재까지 다 들은(맨 마지막 트랙까지 들은) 앨범 중 가장 만족도가 높은 $d_i$을 따로 저장한다.($=closed$)

$i$를 현재 탐색하고 있는 coolness의 앨범 번호라고 하면

$d_i=max(d_i+1,closed+1)$가 된다. ($i$앨범의 이전 coolness보다 크므로 $d_i+1$, 이미 다 들은 앨범의 가장 큰 만족도보다 크므로 $closed+1$)

만약 현재 coolness가 그 앨범 $i$의 마지막 번호라면

$closed=max(closed, d_i)$로 갱신해준다.

완료하면 $d$내에서 가장 큰 수가 최대 만족도가 된다.