백준 1744번 자바 ☆

문제

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

1744번: 수 묶기

 

1. 접근 방식

그리디 문제를 여러번 풀면서 dp문제들과 마찬가지로 처음 접근 방식이 매우 중요하다고 느꼈다.

해당 문제도 처음 접근 방식이 타당하지 못해 많이 헤맨 문제다.

 

처음 나의 접근은 모든 수를 우선순위 큐에 삽입 후 분기별로 순차적으로 묶어 나가며 해결을 했다. 또 전체 배열의 길이가 홀수이냐 짝수이냐로 나눠서 두가지 중 큰 값을 선택하게 했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {

	static int N; 
	static int[] temp;
	static PriorityQueue<Integer> pq;
	static PriorityQueue<Integer> reversePq;
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		temp = new int[N];
		if (N%2 != 0) {
			reversePq = new PriorityQueue<Integer>(Collections.reverseOrder());
		}
		pq = new PriorityQueue<Integer>();
		for (int i=0; i<N; i++) {
			temp[i] = Integer.parseInt(br.readLine());
		}
		
		if (N%2 != 0) {
			for (int i=0; i<N; i++) {
				pq.add(temp[i]);
				reversePq.add(temp[i]);
			}	
		} else {
			for (int i=0; i<N; i++) {
				pq.add(temp[i]);
			}	
		}
		if (N%2 != 0) {
			System.out.println(Math.max(findMaxSum(pq), findMaxSum(reversePq)));
			return;
		} 
		System.out.println(findMaxSum(pq));
	}
	
	public static int findMaxSum(PriorityQueue<Integer> pq) {
		int sum = 0;
		while (pq.size() > 1) {
			int first = pq.poll();
			int second = pq.poll();
			
			if (first > 1 && second > 1) {
				sum += first * second;
				continue;
			}
			if (first == 1 && second == 1) {
				sum += first + second;
				continue;
			}
			if (first < 0 && second < 0) {
				sum += first * second;
				continue;
			}
			if (first < 0 || second < 0) {
				if (first == 0 || second == 0) {
					sum += first * second;
					continue;
				}
				sum += first + second;
				continue;
			}
			sum += first + second;
		}
		if (!pq.isEmpty()) {
			sum += pq.poll();		
		}
		return sum;
	}
}

하지만 분기를 설정한다 해도 순차적으로 묶음을 진행하면 매번 최선의 해가 나올 수 없단것을 간과했다.

결국 이 문제는 항상 최선의 해가 나올 수 있도록 값의 저장을 처음부터 분기를 통해 나눠야 했다.

 

음수 x 음수 => 양수

1 x 1 <  1 + 1 

양수 x 0 < 양수 + 0

음수 x 0 > 음수 + 0

2이상의 양수 x 1 < 2이상의 양수 + 1

 

위 처럼 필요한 분기들을 생성하면 처음 저장 할 때 음수, 양수, 0, 1을 따로 저장할 필요가 있다는 사실을 알게 된다.

 

2. 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {

	static int N; 
	static PriorityQueue<Integer> plusPq;
	static PriorityQueue<Integer> minusPq;
	static int sum;
	static int zero = 0;
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		plusPq = new PriorityQueue<Integer>(Collections.reverseOrder());
		minusPq = new PriorityQueue<Integer>();
		
		for (int i=0; i<N; i++) {
			int temp = Integer.parseInt(br.readLine());
			if (temp >= 1) {
				plusPq.add(temp);
				continue;
			} 
			if (temp < 0) {
				minusPq.add(temp);
				continue;
			}
			zero++;
		}
		
		findMaxSum(plusPq);
		findMaxSum(minusPq);
		System.out.println(sum);
	}
	
	public static void findMaxSum(PriorityQueue<Integer> pq) {
		while (pq.size() > 1) {
			int first = pq.poll();
			int second = pq.poll();
			if (first == 1 || second == 1) {
				sum += first + second;
				continue;
			}
			sum += first * second;
		}
		if (!pq.isEmpty()) {
			if (zero > 0 && pq.peek() < 0) {
				sum += pq.poll() * 0;
				zero--;
				return;
			}
			sum += pq.poll();
			return;
		}
	}
}

 

정리 : 

그리디 알고리즘 자체는 어렵지 않지만 문제를 접근함에 있어서 자꾸 옳지 않은 방향으로 간다. 아마 초반에 문제를 분석할 때 더 많은 경우를 생각하지 않아서 그런듯하다. 시간제한을 두고 풀다보니 어쩔 수 없겠지만 그래도 문제를 최대한 잘게 나눠서 생각하도록 하자.