Codeforces Round #796 (Div. 2) D. The Enchanted Forest

https://codeforces.com/contest/1688/problem/D

조금 긴 방법으로 구현해서 풀었는데, 자꾸 WA가 나오길래 풀이를 좀 더 간편하게 해서 업 솔빙을 해봤다.

그래도 WA가 뜨길래 더 이상 코드를 짧게 할 구간도 없고 long long 도 써서 문제가 없었다.

하지만 long long을 전부 썼지만 첫 입력인 원소의 개수 n는 int로 받았었다.

중간에 1부터 n까지의 합을 구할 때 n을 제곱을 한 것이었다. ( 당연히 오버플로우.. )

고치고 AC. 다음부터는 원소의 개수를 받는 변수도 오버플로우를 잘 생각해야겠다.

 

문제 풀이는 간단하다. k가 n보다 작으면 길이가 k인 최대 구간을 구하면 된다.

k가 n보다 클 때가 문제인데, 잘 생각해보면 처음 주어진 버섯은 어차피 다 먹게 된다.

그러므로 후에 자라나는 버섯만 더해주면 된다.

한 번 먹을 때마다 n개의 버섯이 자라게 된다.

그 n 개는 나중에 먹게 될 n개이므로 그냥 n을 더해주면 된다.

k번째에 거의 다다를 쯤에는 버섯이 전부 자라나도 n-1개밖에 미래에 먹지 못하게 된다.

그다음은 n-2개밖에 먹지 못하게 된다.

결국 정답은 배열 전체합에다가 다음 식을 더해주면 된다.

n + n + n + (n-1) + (n-2) + (n-3) + ... + 2 + 1

항이 k-1개 이므로 잘 계산해 주면 된다.