오답노트 #1744 : 수 묶기

풀이방법 및 문제점

2022.05.07

문제 없이 알고리즘을 잘 짰다고 생각했는데 50%에서 계속 막힌다.

정답이 2의 31제곱 미만이라는 것을 보고 화끈하게 BigInteger로 다루어보았는데 그래도 똑같이 50%에서 틀린다.

흠...

내가 놓친 분기 또는 반례가 있는 것 같다.

모든 가능한 분기를 하나하나 적어가며 빈틈없이 만들어봐야 하나?

거의 다 왔다는 생각이 들어 구글링하기가 아깝다.

 

알고리즘은 다음과 같다.

 

음수와 양수를 따로 다룬다.

 

음수의 경우 다음과 같이 다룬다.

가장 작은 수 즉 절댓값이 큰 것들부터, 모든 음수를 짝짓는다.

주어진 수들 중 음수가 -1, -5, -2, -7 이렇게 네 개라면

(-7, -5), (-2, -1) 이런 식으로 짝짓는 것이다.

만약 음수가 홀수 개라면 가장 절댓값이 작은 수는 짝지어지지 않는 채로 남는다.

만약 음수가 홀수 개인데 주어진 수들 중 0이 존재한다면 가장 절댓값이 작은 수는 0과 짝지어진다.

 

양수의 경우 다음과 같이 다룬다.

가장 큰수부터 모든 양수를 짝짓는다. 위에서 음수를 다룬 것과 유사하다.

그러나!

주어진 수들 중 1이 존재한다면 1은 절대 다른 수와 짝지어서는 안 된다.

1을 다른 수와 짝짓는 순간 1만큼의 손해가 발생하기 때문이다.

가장 큰 양수부터 차례차례 모든 1이 아닌 양수를 서로 짝지으면 된다.

그리고 양수는 0과 짝지으면 안 된다.

 

코드

Java(2022.05.04(int형 변수 sum을 사용))

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{
		// TODO Auto-generated method stub
		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 sum = 0;
		
		//음수부터 다루기
		//작은 음수부터 오름차순으로 다루기
		int idx = 0;
		while(true) {
			//모든 수를 다룬 경우 그냥 정답을 출력하고 끝내기
			if(idx == n-1) {
				sum += arr[idx];
				System.out.print(sum);
				System.exit(0);
			}
			else if(idx == n) {
				System.out.print(sum);
				System.exit(0);
				break;
			}
			
			
			
			
			//이번 수와 다음 수가 모두 음수인 경우
			if(arr[idx] < 0 && arr[idx+1] < 0) {
				//음수끼리는 제일 작은 놈들부터 묶음
				sum += arr[idx]*arr[idx+1];
				idx += 2;
			}
			//이번 수는 음수, 다음 수는 0인 경우
			else if(arr[idx] < 0 && arr[idx+1] == 0) {
				//음수가 홀수 개이고 0이 존재할 경우 가장 큰 음수와 0을 짝지음
				idx += 2;
				break;
			}
			//이번수는 음수, 다음 수는 양수
			else if(arr[idx] < 0 && arr[idx+1] > 0) {
				//음수와 양수는 짝지으면 안 됨
				//짝짓지 않은 상태의 음수를 결과값에 더해주고 break
				sum += arr[idx];
				idx++;
				break;
			}
			
			//0 또는 양수가 등장하면 break해야 함
			//1) 0이 존재하는데 음수와 묶이지 않은 경우
			//0이 양수와 곱해지는 일이 없도록 idx를 1 증가시켜 양수를 다룰 때 0을 무시하도록 해야 함
			else if(arr[idx] == 0) {
				idx++;
				break;
			}
			//2) 양수가 등장했거나, 0이 존재하는데 묶을 음수가 없는 경우 그냥 break
			else break;
		}
		
		//그 다음 양수 다루기
		//큰 양수부터 내림차순으로 묶기
		for(int i = n-1; i>=idx; i--) {
			if(arr[i-1] == 1) {
				//1은 묶으면 안 됨
				//묶지 않은 상태에서 두 수 덧셈하기
				sum += arr[i];
				sum += 1;
				i--;
			}
			else if(i == idx) {
				//양수가 홀수 개이면 가장 작은 양수는 짝 없이 그냥 더해주고 break
				sum += arr[i];
				break;
			}
			else {
				//큰놈들부터 짝지어주기
				sum += arr[i]*arr[i-1];
				i--;
			}
		}
		
		System.out.print(sum);
	}

}

 

Java(2022.05.07(BigInteger형 변수 sum을 사용))

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		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);
		
		//수들의 합(정답)
		BigInteger sum = new BigInteger("0");
		
		//음수부터 다루기
		//작은 음수부터 오름차순으로 다루기
		int idx = 0;
		while(true) {
			//모든 수를 다룬 경우 그냥 정답을 출력하고 끝내기
			if(idx == n-1) {
				sum = sum.add(new BigInteger(Integer.toString(arr[idx])));
				System.out.print(sum);
				System.exit(0);
			}
			else if(idx == n) {
				System.out.print(sum);
				System.exit(0);
				break;
			}
			
			
			
			
			//이번 수와 다음 수가 모두 음수인 경우
			if(arr[idx] < 0 && arr[idx+1] < 0) {
				//음수끼리는 제일 작은 놈들부터 묶음
				sum = sum.add(new BigInteger(Integer.toString(arr[idx]*arr[idx+1])));
				idx += 2;
			}
			//이번 수는 음수, 다음 수는 0인 경우
			else if(arr[idx] < 0 && arr[idx+1] == 0) {
				//음수가 홀수 개이고 0이 존재할 경우 가장 큰 음수와 0을 짝지음
				idx += 2;
				break;
			}
			//이번수는 음수, 다음 수는 양수
			else if(arr[idx] < 0 && arr[idx+1] > 0) {
				//음수와 양수는 짝지으면 안 됨
				//짝짓지 않은 상태의 음수를 결과값에 더해주고 break
				sum = sum.add(new BigInteger(Integer.toString(arr[idx])));
				idx++;
				break;
			}
			
			//0 또는 양수가 등장하면 break해야 함
			//1) 0이 존재하는데 음수와 묶이지 않은 경우
			//0이 양수와 곱해지는 일이 없도록 idx를 1 증가시켜 양수를 다룰 때 0을 무시하도록 해야 함
			else if(arr[idx] == 0) {
				idx++;
				break;
			}
			//2) 양수가 등장했거나, 0이 존재하는데 묶을 음수가 없는 경우 그냥 break
			else break;
		}
		
		//그 다음 양수 다루기
		//큰 양수부터 내림차순으로 묶기
		for(int i = n-1; i>=idx; i--) {
			if(arr[i-1] == 1) {
				//1은 묶으면 안 됨
				//묶지 않은 상태에서 두 수 덧셈하기
				sum = sum.add(new BigInteger(Integer.toString(arr[i] + 1)));
				i--;
			}
			else if(i == idx) {
				//양수가 홀수 개이면 가장 작은 양수는 짝 없이 그냥 더해주고 break
				sum = sum.add(new BigInteger(Integer.toString(arr[i])));
				break;
			}
			else {
				//큰놈들부터 짝지어주기
				sum = sum.add(new BigInteger(Integer.toString(arr[i]*arr[i-1])));
				i--;
			}
		}
		
		System.out.print(sum);
	}

}