[백준(Baekjoon)][자바(java)] 1744 : 수 묶기 / 그리디

 

www.acmicpc.net/problem/1744

1744번: 수 묶기

 

문제 풀이

 

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() ), sum = 0, l, r, x, y;
		int a[] = new int[n];
		for( int i = 0; i < n; i++ )
			a[i] = Integer.parseInt( br.readLine() );
		br.close();
		
		Arrays.sort( a );
		for( l = 0; l < n-1; l += 2 ) {
			x = a[l];
			y = a[l+1];
			if( x < 1 && y < 1 )
				sum += x * y;
			else break;
		}
		for( r = n-1; r > 0; r -= 2 ) {
			x = a[r];
			y = a[r-1];
			if( x > 1 && y > 1 )
				sum += x * y;
			else break;
		}
		for( ; l <= r; l++ )
			sum += a[l];
		
		System.out.println( sum );
		
	}

}

 

*  그리디

-  수를 두 개씩 묶어( 곱하여 ) 합이 최대가 되려면
   두 수가 1보다 크거나, ex) 3 * 5 = 15
   두 수가 1보다 작아야 한다 ex) -2 * -5 = 10
  ( n * 0 = 0 이므로 이때의 n은 음수여야 함 )
-  수가 1일 때는 묶지 않고 따로 더해줘야 함
  ( n * 1 = n 이므로 이때는 수를 묶지 않아야 함 )