455A. Boredom

코드포스에는 왜 이리 지루한 사람이 많은가?

Problem - 455A - Codeforces

---

지문이 헷갈리기 쉽게 쓰여 있어서, 일단 문제를 정확히 이해하자. 

 

$n$개의 정수 $a_{1},~a_{2},~\cdots,~a_{n}$이 있다. 임의의 $a_{k}$를 골라 지우고, 모든 $a_{k}-1$과 $a_{k}+1$을 지운다. 예를 들어 $2$를 하나 지웠다면 모든 $1$과 $3$도 지워야 한다. 이때 얻을 수 있는 점수는 $a_{k}$점이다.

 

수를 하나 지우면 양 옆의 수도 없어져서 골치아픈 문제이다. 만약 $a_{k}-1$만 지워지는 조건이었다면 골드 하위 수준의 문제였을 것이다.

 

그러나 아주 간단한 제한을 걸면 이 문제 역시 골드 하위급으로 만들어버릴 수 있다. 바로 수를 오름차순(또는 내림차순)으로 고르는 것이다. 수를 오름차순으로 고르면 $a_{k}+1$만 지워지는 효과가 있고, 내림차순으로 고르면 $a_{k}-1$만 지워지는 효과가 있다. 이렇게 선택의 방향을 제한하면 문제를 쉽게 만들 수 있다.

 

주어진 수열을 정렬한 후, 내림차순으로 골라 보자. $a_{k}$를 고를 때 얻는 점수는 $a_{k} \times count[a_{k}]$에 $[1,~a_{k}-2]$ 구간에서 얻을 수 있는 점수를 더한 값이다. $a_{k}$를 고르지 않을 때 얻는 점수는 $[1,~a_{k}-1]$ 구간에서 얻을 수 있는 점수와 같다. 이 조건을 식으로 완성하면 된다.

---

자주 쓰이는 발상이므로 잘 기억하자.