Informatica Online Judge

  동전 줍기 2 [0988 / 03DC]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 20   Total Tried : 48


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[JKJeong 2014]

Background

경곽이는 본관에서 SRC로 가는 길에 연못을 지나다가 신기한 관경을 목격했다.

연못에서 산신령이 나타나 경곽이에게 말하길...

"경곽아 내가 이 연못의 주변에 원형으로 동전을 N개 놓아 두었다. 이 중 K개를 가져가도록 하여라. 단, 3개의 동전을 연속해서 가져갈 수 는 없다."

라고 하였다.

산신령은 N개의 동전을 연못의 둘레에 원형으로 두었으며, 각 i번째 동전의 가치는 wi라고 한다. 이 중 연속하여 3개 이상은 가져갈 수 없을 때, 경곽이가 가져갈 수 있는 동전의 최대 가치를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 동전의 수 N과 가져갈 수 있는 동전의 수 K를 공백으로 구분하여 입력된다.
둘 째줄에 각 N개의 동전의 가치 wi가 공백으로 구분되어 입력된다.

[입력값의 정의역]
3 <= N <= 2,000
1 <= K <= N
1 <= wi <= 1,000

[Sub-task Info]
#1 : N <= 50
#2 : N <= 100
#3 : N <= 1,000
#4 : N <= 2,000

Output

첫 번째 줄에 얻을 수 있는 최대 이익을 출력한다. 단, 조건을 만족하면서 얻을 수 있는 방법이 없다면 0을 출력한다.

IO Example

입력
4 2
1 2 3 4

출력
7

* 설명 : 최대 가치는 3과 4를 가져가는 7이다.

입력2
6 3
6 5 1 2 3 4

출력2
14

* 설명 : 3, 6, 5의 3개를 가져가는 것이 가장 이득이다. 6, 5, 4를 가져갈 수는 없다. 4는 맨끝이지만 원형이기 때문에 6과 연결되므로, 연속으로 3개를 가져가는 결과가 되어 최대는 3+6+5 = 14가 된다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]