[Java] 백준 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이 되어 최대가 된다.

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

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

입력

첫째 줄에 수열의 크기 N이 주어진다. N은 50보다 작은 자연수이다. 둘째 줄부터 N개의 줄에 수열의 각 수가 주어진다. 수열의 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 231보다 작다.

예제 입력 1

4
-1
2
1
3

예제 출력 1

6

예제 입력 2

6
0
1
2
4
3
5

예제 출력 2

27

예제 입력 3 

1
-1

예제 출력 3

-1

예제 입력 4

3
-1
0
1

예제 출력 4

1

예제 입력 5

2
1
1

예제 출력 5

2

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

	private static BufferedReader br;
	
	private static int N;
	private static List<Integer> list=new ArrayList<>();
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		
		for(int i=0;i<N;i++) list.add(Integer.parseInt(br.readLine()));	// 수열을 입력받은 후 오름차순 정렬
		Collections.sort(list);
		
		int cnt=0;
		int begin=0, end=N-1;	// 시작 인덱스와 끝 인덱스
		long result=0;	// 결과값
		while(begin<=end) {	// (시작 인덱스 <= 끝 인덱스)인 동안 반복
			int comp1=0, comp2=0;	// comp1: 앞에서 2개의 수를 곱한 값, comp2: 뒤에서 2개의 수를 곱한 값
			if(begin==end) {	// 시작 인덱스와 끝 인덱스가 같아지면 해당 값을 결과값에 더해주고 반복문 끝남
				result+=list.get(begin);
				break;
			}
			if(begin+1<=end) {	// 앞에서 2개 계산 가능한 경우
				int s1=list.get(begin);
				int s2=list.get(begin+1);
				if(s1*s2<0) {	// 앞에서 2개의 곱이 음수이면 첫번째 수만 결과값에 더해줌
					result+=s1;
					begin++;
				} else if(s1*s2==0 && (s1<0 || s2<0)) {	// 앞에서 2개의 수 중 하나는 음수, 하나는 0이면 곱한 값을 결과값에 더해줌
					begin+=2;
				} else {	// 앞에서 2개의 곱이 양수이면
					if(s1==1 || s2==1) {	// 두 수 중 하나가 1이면 결과값에 더해줌
						result+=s1;
						begin++;
					} else comp1=s1*s2;	// 두 수가 모두 1보다 크면 곱한 값을 결과값에 더해줌
				}
			}
			if(end-1>=begin) {	// 뒤에서 2개 계산 가능한 경우
				int e1=list.get(end-1);
				int e2=list.get(end);
				if(e1*e2<=0) {	// 뒤에서 2개의 곱이 음수이면 끝 수만 결과값에 더해줌
					result+=e2;
					end--;
				} else if(e1*e2==0 && (e1<0 || e2<0)) {	// 뒤에서 2개의 수 중 하나는 음수, 하나는 0이면 곱한 값을 결과값에 더해줌
					end-=2;
				} else {	// 뒤에서 2개의 곱이 양수이면
					if(e1==1 || e2==1) {	// 두 수 중 하나가 1이면 결과값에 더해줌
						result+=e2;
						end--;
					} else comp2=e1*e2;	// 두 수가 모두 1보다 크면 곱한 값을 결과값에 더해줌
				}
			}
			if(comp1>0 || comp2>0) {	// 앞의 2개 곱과 뒤의 2개 곱 중 양수가 존재하는 경우, 둘 중 더 큰 값을 결과값에 저장
				if(comp1>comp2) {
					result+=comp1;
					begin+=2;
				} else {
					result+=comp2;
					end-=2;
				}
			}
		}
		
		System.out.println(result);
	}

}

1. 입력 수열을 오름차순 정렬합니다.

2. 앞에서 2개를 묶어준 경우와 뒤에서 2개를 묶어준 경우를 각각 고려합니다.

    2-1. 곱이 음수인 경우 : 현재 인덱스의 값 하나만 결과값에 더합니다.

    2-2. 곱이 0인 경우 : 두 개의 수 중 음수가 존재하면 두 수의 곱인 0을 결과값에 더합니다.

    2-3. 곱이 양수인 경우

        2-3-1. 두 수 중 1이 존재하는 경우 : 1은 곱보다 합이 더 값을 크게 만들기 때문에 현재 인덱스의 값 하나만 결과값에 더합니다.

        2-3-2. 두 수 중 1이 존재하지 않는 경우 : 두 수의 곱을 결과값에 더합니다.

3. 위 과정을 (앞 인덱스<=뒤 인덱스)인 동안 반복합니다.

    3-1. (앞 인덱스=뒤 인덱스)인 경우, 해당 값을 결과값에 더해주고 반복문을 빠져나옵니다.