백준 11908번 카드 java 풀이

문제

승현이는 앞면과 뒷면이 있는 카드 n장을 가지고 있습니다. 각 카드의 앞면에는 1 이상 2222 이하의 정수가 적혀 있으며, 이 수는 카드마다 서로 다릅니다. 각 카드의 뒷면에는 동물 그림이 그려져 있으며, 이 그림 역시 카드마다 서로 다릅니다.

가능한 카드의 예시입니다. 왼쪽 그림은 앞면, 오른쪽 그림은 뒷면입니다.

승현이는 카드들을 바닥에 뒷면이 보이도록 일렬로 늘어 놓고, 차례대로 1 이상 n 이하의 자연수 번호를 붙였습니다. 이 중 i번 카드의 앞면에 적혀 있는 수를 ci로 둡시다. 승현이는 바닥에 카드가 정확히 한 장 남을 때까지 아래와 같은 행동을 반복합니다.

1. 승현이는 마음에 드는 서로 다른 카드 두 장을 앞면이 보이도록 뒤집어 봅니다.
2. 승현이는 앞면에 더 작은 수가 적혀 있는 카드를 주머니 속에 넣고, 더 큰 수가 적혀 있는 카드는 다시 바닥에 뒷면이 보이도록 내려놓습니다.
3. 카드가 두 장 이상 남았다면 1번으로 돌아갑니다. 카드가 정확히 한 장 남았다면, 승현이는 주머니 속에 있는 카드들을 꺼내 앞면에 적혀 있는 수들의 합을 구합니다.

승현이는 큰 수가 좋아서, 마지막에 주머니 속에 들어있는 카드들에 적혀 있는 수들의 합을 가능한 한 크게 하고자 합니다. (뒷면에 그려진 동물 그림이 서로 다르므로 방법만 알고 있다면 충분히 가능합니다!) 승현이를 도와주세요.

입력

첫 번째 줄에 카드의 수를 나타내는 자연수 n이 주어집니다. (1 ≤ n ≤ 2222)

두 번째 줄에 c1,c2,⋯,cn이 공백을 사이에 두고 차례대로 주어집니다.

출력

첫 번째 줄에 가능한 최대 합을 출력합니다.

 

예제 입력 1 복사

2
3 4

예제 출력 1 복사

3

예제 입력 2 복사

3
1 3 5

예제 출력 2 복사

4

예제 입력 3 복사

20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

예제 출력 3 복사

190

힌트

예제 1에서 가능한 경우는 한 가지 뿐입니다.

승현이는 3이 적힌 카드와 4가 적힌 카드를 뽑게 되고, 3이 적힌 카드를 갖고 나면 남은 카드가 한 장밖에 없으므로 답은 3이 됩니다.

예제 2에서 가능한 경우는 세 가지입니다.

• 승현이가 처음에 1이 적힌 카드와 3이 적힌 카드를 뽑고, 다음에 3이 적힌 카드와 5가 적힌 카드를 뽑았을 경우 답은 1+3=4가 됩니다.
• 승현이가 처음에 1이 적힌 카드와 5가 적힌 카드를 뽑고, 다음에 3이 적힌 카드와 5가 적힌 카드를 뽑았을 경우 답은 1+3=4가 됩니다.
• 승현이가 처음에 3이 적힌 카드와 5가 적힌 카드를 뽑고, 다음에 1이 적힌 카드와 5가 적힌 카드를 뽑았을 경우 답은 3+1=4가 됩니다.

따라서 답은 4가 됩니다.

 

 

간단한 구현 문제였다.

import java.io.*;
import java.sql.Array;
import java.util.*;
import java.util.stream.Collectors;

public class Main {


    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(System.in);

        int n = 0;
        n = sc.nextInt();

        List<Integer> arr = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            arr.add(sc.nextInt());
        }

        arr.sort(Comparator.naturalOrder());


        int ans = 0;
        for (int i = 0; i < n - 1; i++) {
            ans += arr.get(i);
        }

        System.out.println(ans);

    }
}