[Greedy] BOJ 1744 수 묶기 (Java)

https://www.acmicpc.net/problem/1744

1744번: 수 묶기

문제 분석

수열 N이 주어졌을 때, 수열의 두 수를 묶어서 (순서는 상관없음) 묶은 수들의 합이 최대가 되도록 하는 문제.

묶은 두 수는 곱해지며, 수는 한 번만 묶을 수 있고, 묶지 않을 수도 있다.

---

예전에 풀었던 문제인데 뭔가 greedy 하지 못하다는 생각이 들어 백준에서 더 깔끔하게 푸신 분들이 없나 참고하였다.

내 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        List<Integer> positive = new ArrayList<>();
        List<Integer> negative = new ArrayList<>();
        List<Integer> isone = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            int n = Integer.parseInt(br.readLine());
            if (n == 1) isone.add(n);
            if (n > 1) positive.add(n);
            else if (n <= 0) negative.add(n);
        }

        Collections.sort(positive, Collections.reverseOrder()); // 양수는 내림차순 정렬
        Collections.sort(negative); // 음수는 오름차순 정렬

        int sum = 0;

        if(positive.size() % 2 == 0) {
            for(int i=0; i<positive.size() - 1; i+=2)
                sum += positive.get(i) * positive.get(i+1);
        } else {
            for(int i=0; i<positive.size() - 2; i+=2)
                sum += positive.get(i) * positive.get(i+1);
            sum += positive.get(positive.size() - 1);
        }

        if(negative.size() % 2 == 0) {
            for(int i=0; i<negative.size() - 1; i+=2)
                sum += negative.get(i) * negative.get(i+1);
        } else {
            for(int i=0; i<negative.size() - 2; i+=2)
                sum += negative.get(i) * negative.get(i+1);
            sum += negative.get(negative.size() - 1);
        }

        sum += isone.size();

        System.out.println(sum);
    }
}

내가 접근한 방식이다.

• 0, 1은 예외처리를 해줘야 한다. (1은 묶지 않고, 0은 만약 음수가 있다면 하나 남은 음수와 묶기)
• 음수가 2개 이상일 경우, 음수끼리 묶고 하나 남은 음수는 0이랑 묶기 (음수끼리도 작은 수부터 차례로 묶기)
• 양수의 경우, 큰 수부터 차례대로 짝지어서 묶기
• 묶은 수들을 다 더해준다.

이 방식도 greedy 해 보이긴 하지만 뭔가 어정쩡하고 노가다성이 짙은 느낌이 들었다.

그러던 중 굉장히 깔끔하고 누가 봐도 greedy 한 코드가 있어 참고해봤다.

참고한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

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

        Arrays.sort(arr);

        int[] answer = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            answer[i] = arr[i - 1] + answer[i - 1];
            if (i > 1) {
                answer[i] = Math.max(answer[i], answer[i - 2] + (arr[i - 2] * arr[i - 1]));
            }
        }

        System.out.println(answer[N]);
    }
}

접근 방식은 이와 같다.

• 수열을 오름차순으로 정렬한다.
• answer[i]에 일단 수열의 i - 1 번 값과 이전 i - 1 번 정답을 더한 값을 저장한다.
• 일단 넣은 값과 전의 전값과 수열의 i - 1번 값과 i - 2번 값을 묶은 값을 더한 값 중 더 큰 값을 i 번째 정답으로 업데이트한다.

수열을 오름차순으로 정렬했기 때문에 수열의 이전 값이 이후 값보다 클 수 없어 정당성에도 문제가 없다.

 

greedy나 DP 문제는 머리를 정말 잘 써야 하겠다...