시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 32 MB | 782 | 605 | 564 | 78.008% |
승현이는 앞면과 뒷면이 있는 카드 n장을 가지고 있습니다. 각 카드의 앞면에는 1 이상 2222 이하의 정수가 적혀 있으며, 이 수는 카드마다 서로 다릅니다. 각 카드의 뒷면에는 동물 그림이 그려져 있으며, 이 그림 역시 카드마다 서로 다릅니다.
가능한 카드의 예시입니다. 왼쪽 그림은 앞면, 오른쪽 그림은 뒷면입니다.
승현이는 카드들을 바닥에 뒷면이 보이도록 일렬로 늘어 놓고, 차례대로 1 이상 n 이하의 자연수 번호를 붙였습니다. 이 중 i번 카드의 앞면에 적혀 있는 수를 ci로 둡시다. 승현이는 바닥에 카드가 정확히 한 장 남을 때까지 아래와 같은 행동을 반복합니다.
승현이는 큰 수가 좋아서, 마지막에 주머니 속에 들어있는 카드들에 적혀 있는 수들의 합을 가능한 한 크게 하고자 합니다. (뒷면에 그려진 동물 그림이 서로 다르므로 방법만 알고 있다면 충분히 가능합니다!) 승현이를 도와주세요.
첫 번째 줄에 카드의 수를 나타내는 자연수 n이 주어집니다. (1 ≤ n ≤ 2222)
두 번째 줄에 c1,c2,⋯,cn이 공백을 사이에 두고 차례대로 주어집니다.
첫 번째 줄에 가능한 최대 합을 출력합니다.
2 3 4
3
3 1 3 5
4
20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
190
예제 1에서 가능한 경우는 한 가지 뿐입니다.
승현이는 3이 적힌 카드와 4가 적힌 카드를 뽑게 되고, 3이 적힌 카드를 갖고 나면 남은 카드가 한 장밖에 없으므로 답은 3이 됩니다.
예제 2에서 가능한 경우는 세 가지입니다.
따라서 답은 4가 됩니다.