백준 1744번) 수 묶기 JAVA

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

1744번: 수 묶기

 

#문제 

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.

예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

 

#알고리즘

그리디,정렬

 

#난이도

Gold4

 

#풀이방법

처음로 그리디 문제의 높은 난이도를 푼 것 같다. 그리디라고 해서 뭔가 사고적인 능력과 뛰어난 머리가 필요할 것 같았지만, 의외로 조금만(?) 생각해보면 풀 수 있었던 문제였던 것 같다.

 

문제를 좀 더 요약하자면 경우의 수 2가지가 있다. 두수를 묶거나 or 더해주거나..

이 2가지 경우를 이용해서 그리디적으로 합의 최댓값을 도출해내면 된다.

 

문제를 풀면서 오답률이 20프로인 이유가 있구나라는 생각이 많았다. 예외 케이스가 너무 많았다.

따라서 예외 케이스를 고려해가며, 코드를 짜야만 했다.

 

나같은 경우는 양수,음수,1,0이렇게 4가지 경우를 arraylist를 선언하여 정렬하였다.

arraylist를 선언한 이유는 크기에 상관없이 데이터를 계속 더하고 무언가 유동적으로 데이터를 관리할 수 있기 때문에

배열이 아닌 arraylist를 사용하였고,  음수,양수,0,1 이렇게 4가지로 경우의 수를 나눈 이유는 다음과 같다.

 

양수: 우리가 흔히 생각하는 양수의 특징이다.

이같은 경우는 내림차순으로 정렬하여, 큰 순으로 2개씩 곱해서 더해주면 최대의 합을 도출해 낼 수 있다.

만약 홀수라서 묶이는 것이 아닌 남는 수가 있으면 그냥 더해주면 된다.

 

		Collections.sort(plus,Collections.reverseOrder());
		//내림차순으로 정렬
		
		for(int i=0; i<plus.size();) {
			
			if(i+1 < plus.size()) {
				sum += plus.get(i) * plus.get(i+1);
				i+=2;
			}//양수의 개수가 짝수라면 그냥 2개씩 더해주면 된다.
			else {
				sum += plus.get(i);
				i++;
			}//양수의 개수가 홀수라서 남는 수가 있다면 그냥 더해준다.
			
		}

 

 

음수: 음수끼리 곱하면 양수가 돼서 최종 sum의 합이 더 커지게 된다.

여기서 minus_surplus 변수를 선언한 것은 만약 음수의 크기가 짝수라면 오름차순으로 정렬하여 2개씩 묶어 sum을

늘려주면 되지만, 홀수인경우 무조건 하나가 남게 된다.

문제는 이 남는 것을 그냥 더하냐?...? 

아니다. 방금 우리가 선언했던 것 양수,음수,0,1에 arraylist등

0의 특징은 n x 0 = 0이기 때문에 그냥 더해주기보다 0이 있는지 확인한후 있으면 곱해서 상쇄되기 때문에 음수를 더해주지 않지만, 만약 0이 없다면 따른 방법이 없기 때문에 sum에 더해준다.

 

1: 1은 무엇을 곱해도 값이 똑같아진다 ex)100000 * 1 = 100000 따라서 1은 곱하기보다는 더해주는 것이 sum을 크게 만드는 방법이다.

 

//음수가 짝수인경우 생각
		Collections.sort(plus,Collections.reverseOrder());
		//내림차순으로 정렬
		
		for(int i=0; i<plus.size();) {
			
			if(i+1 < plus.size()) {
				sum += plus.get(i) * plus.get(i+1);
				i+=2;
			}//양수의 개수가 짝수라면 그냥 2개씩 더해주면 된다.
			else {
				sum += plus.get(i);
				i++;
			}//양수의 개수가 홀수라서 남는 수가 있다면 그냥 더해준다.
			
		}
		
		Collections.sort(minus);//오름차순 정렬 
		//why? 음수이기 때문이다. 절댓값을 큰것을 보고 정렬
		
		int minus_surplus = 0;
		//만약 음수의 크기가 짝수인경우는 2개씩 곱해주면된다.
		//음수의 특징 음수끼리 곱하면 양수가 됨
		
		for(int i=0; i<minus.size();) {
			
			if(i+1 < minus.size()) {
				sum += minus.get(i) * minus.get(i+1);
				i+=2;
			}
			else {
				minus_surplus = minus.get(i);
				i++;//홀수인경우 minus_surplus에 저장
			}
		}
			
		if(minus_surplus != 0) {
			if(zero.isEmpty()) {
				sum += minus_surplus;
			}
		}//만약 홀수라서 minus_surplus가 있는경우, 0이 있는지 확인하고,

 

#전체 코드

import java.util.*;
//1t

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		
		int sum = 0;
		
		ArrayList<Integer> plus = new ArrayList<>();//+
		ArrayList<Integer> minus = new ArrayList<>();//-
		ArrayList<Integer> zero = new ArrayList<>();//0
		ArrayList<Integer> one = new ArrayList<>();//1
		//arraylist 배열 4가지 선언 plus,minus,0,1
		
		for(int i=0; i<N; i++) {
			
			int n = sc.nextInt();
			
			if(n > 1) {
				plus.add(n);
			}//양수
			else if(n < 0) {
				minus.add(n);
			}//음수
			else if(n == 1) {
				one.add(1);
			}//1인경우
			else {
				zero.add(0);
			}//0인경우
			
		}//4가지 경우의 수로 따로 분리
		
		//음수가 짝수인경우 생각
		Collections.sort(plus,Collections.reverseOrder());
		//내림차순으로 정렬
		
		for(int i=0; i<plus.size();) {
			
			if(i+1 < plus.size()) {
				sum += plus.get(i) * plus.get(i+1);
				i+=2;
			}//양수의 개수가 짝수라면 그냥 2개씩 더해주면 된다.
			else {
				sum += plus.get(i);
				i++;
			}//양수의 개수가 홀수라서 남는 수가 있다면 그냥 더해준다.
			
		}
		
		Collections.sort(minus);//오름차순 정렬 
		//why? 음수이기 때문이다. 절댓값을 큰것을 보고 정렬
		
		int minus_surplus = 0;
		//만약 음수의 크기가 짝수인경우는 2개씩 곱해주면된다.
		//음수의 특징 음수끼리 곱하면 양수가 됨
		
		for(int i=0; i<minus.size();) {
			
			if(i+1 < minus.size()) {
				sum += minus.get(i) * minus.get(i+1);
				i+=2;
			}
			else {
				minus_surplus = minus.get(i);
				i++;//홀수인경우 minus_surplus에 저장
			}
		}
			
		if(minus_surplus != 0) {
			if(zero.isEmpty()) {
				sum += minus_surplus;
			}
		}//만약 홀수라서 minus_surplus가 있는경우, 0이 있는지 확인하고,
		//0이 없다면 sum에 더해줌
		
		sum += one.size();
		//1이 있다면 one의 size만큼 더해준다.
		
		System.out.println(sum);
		
	}

}