21.02.23 [백준] 1744 수 묶기

[blossun]

• 문제

• 묶이는 수의 갯수는 두 개

아이디어

1. 오름차순 정렬
2. 음수, 0, 양수를 기준으로
3. 양수) 최대한 큰 수 끼리 두 수를 서로 곱해 나감
   양수값 주의 사항 - 1과 결합될 때는 곱하지말고 더해야 더 큰값이다.
4. 0 ) 0은 마지막에 음수가 하나 남는다면 0으로 곱해서 없앰
5. 음수 ) 음수 * 음수 = 양수 이므로 최대한 짝수 개는 곱해줌

• 예시

-1 -2 -3 0 1 2 3
→ 
(-1 * 0) + (-2 * -3) + 1 + (2 * 3) = 13

어려운점 & 실수

• 모든 값을 넣고 기본 오름차순 정렬하면
  -1 -3 -2 1 3 2 0 → -3 -2 -1 0 1 2 3 이 된다.
  ⇒ 이 상태에서 뒤에서부터 쭉 계산하면 (-3 * 0) + (-2 * -1) + 1 + (2 * 3)이 된다.
  음수는 별개로 분리 계산

• ⭐️ 주의할 조건 ⭐️
  "1과 2는 곱하는 것 보단 더하는게 더 크다"
  ⇒ 1의 경우에는 곱하지말고 더해야함!!!!
  1 2 ⇒ 3
  1 1 ⇒ 2

정답

public class N11502 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            int[] arr = new int[N];

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }

            long total = 0;
            int max = arr[N - 1];
            for (int i = N - 2; i >= 0; i--) {
                if (arr[i] < max) {
                    total += max - arr[i];
                } else {
                    max = arr[i];
                }
            }
            System.out.println(total);
        }
    }
}

[blossun]

반례

5
3
9
4
3
3
→ 48

2
1
2
⇒ 3

5
-3
-2
-1
1
2
⇒ 8

3
-6
-5
-1
⇒ 29

5
1
1
1
1
1
⇒ 5

13
-10
-9
-8
-7
-6
-5
1
2
3
4
5
6
7
⇒ 245

10
-5
-4
-3
0
1
2
3
4
5
6
⇒ 65

10
-10
-9
-8
-7
-6
0
1
2
3
4
⇒ 161

5
-1
-2
0
0
0
⇒ 2

5
-5
-4
-3
-2
-1
⇒ 25

4
1
1
2
1
⇒ 5

[blossun]

조금 더 깔끔한 풀이

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int zero = 0, one = 0;
		List<Integer> pos = new ArrayList<>();
		List<Integer> neg = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			int n = sc.nextInt();
			if (n > 1)	pos.add(n);
			else if (n == 1) one++;
			else if (n == 0) zero++;
			else	neg.add(n);
		}
		
		Collections.sort(pos);
		Collections.reverse(pos);
		Collections.sort(neg);
		
		int result = 0;
		for (int i = 0; i < pos.size()-1; i+=2)
			result += (pos.get(i)*pos.get(i+1));
		if (pos.size()%2 == 1)	result += pos.get(pos.size()-1);
		
		for (int i = 0; i < neg.size()-1; i+=2) 
			result += (neg.get(i)*neg.get(i+1));
		if (neg.size()%2 == 1 && zero == 0)	result += neg.get(neg.size()-1);
		
		System.out.println(result+one);
	}

}