[백준 1744번] 수 묶기 (java)

1744번: 수 묶기

 

문제 자체는 쉬워보였는데 생각하지도 못한 반례가 몇 개 있어서 시행착오를 겪었다.

 

우선, 양수만 놓고 보면 최대값이 나오기 위해서는 내림차순으로 정렬해서 큰수끼리 차례대로 곱해주면 된다고 생각했다. ex) 5 4 3 2 1 일 경우, (5*4) + (3*2) + 1 = 27

만약에 음수가 존재한다면 음수는 절대 양수와 곱해져서는 안된다. 음수 x 양수는 더 작은 음수가 되기 때문이다. 그래서 음수는 같은 음수와 곱해지거나 혹은, 0과 곱해져서 음수를 상쇄시켜야 한다.

즉 정리하면, 양수는 양수끼리 곱해지고, 음수는 음수끼리(혹은 0) 곱해져야 한다.

 

그래서 양수만 저장하는 리스트와, 음수와 0을 저장하는 리스트 두 개를 만들어서

입력받은 수가 양수인지 음수(혹은 0)인지 판단한 후 알맞은 리스트에 추가해주었다.

List<Integer> pn = new ArrayList<>();

List<Integer> nn = new ArrayList<>();

 

그리고 pn과 nn을 각각 정렬해주어야 하는데, 이 때 양수가 들어있는 pn는 내림차순으로, 음수나 0이 들어있는 nn은 오름차순으로 정렬해준다.

큰수부터 차례대로 두 개씩 짝지어서 곱해줄 것이기 때문에 양수의 경우 가장 큰 수가 왼쪽에 오도록 내림차순으로 정렬하는 것이 맞다. 반면에 음수의 경우 음수와 음수를 곱해서 큰 수를 만들기 위해서는 절대값이 큰 것끼리 곱해야 한다. ex) (-1)*(-2) 보다는 (-5)*(-6) 이 더 크다.

음수는 작을수록 절대값이 크기 때문에 양수와 달리 오름차순으로 정렬을 해서 가장 왼쪽에 있는 수의 절대값이 가장 크도록 정렬한다.

 

정렬 후에 각각의 리스트를 왼쪽에서부터 두 개씩 짝지어서 곱하고, 그 결과를 더해주는 일을 반복한다.

 

예를 들어, -1 -3 -5 0 2 4 6 이 입력된 경우

pn는 정렬한 결과 {6, 4, 2} 이 들어가고, nn은 정렬한 결과 {-5, -3, -1, 0} 이다.

pn에서 두 개씩 짝지어 곱하고, nn에서도 두 개씩 짝지어 곱한 후 각각을 더하면 다음과 같다.

(6*4) + 2 + (-5*-3) + (-1*0) = 24 + 2 + 15 + 0 = 41

		while (i < pn.size()) {
			if (i + 1 < pn.size())
				sum += pn.get(i++) * pn.get(i++);
			else
				sum += pn.get(i++);
		}

		i = 0;
		while (i < nn.size()) {
			if (i + 1 < nn.size())
				sum += nn.get(i++) * nn.get(i++);
			else
				sum += nn.get(i++);
		}

 

그런데 여기서 한 가지 주의해야할 점이 있다.

이 부분 때문에 계속 '틀렸습니다.'가 나와서 한참동안 반례를 생각했다.

양수에서 1의 경우에는 1과 다른 수를 곱하는 것보다 더하는 값이 더 커진다.

1과 2가 있을 때 1*2 = 2 보다 1+2 = 3 이 더 크다. 그러므로 두 값을 곱하기 전에 두 숫자가 모두 1이 아닌지 확인한 후에, 두 수를 곱해야 한다.

pn.get(i) != 1 && pn.get(i+1) != 1

nn.get(i) != 1 && nn.get(i+1) != 1

		while (i < pn.size()) {
			if (i + 1 < pn.size() && pn.get(i) != 1 && pn.get(i + 1) != 1)
				sum += pn.get(i++) * pn.get(i++);
			else
				sum += pn.get(i++);
		}

		i = 0;
		while (i < nn.size()) {
			if (i + 1 < nn.size() && nn.get(i) != 1 && nn.get(i + 1) != 1)
				sum += nn.get(i++) * nn.get(i++);
			else
				sum += nn.get(i++);
		}

 

 

소스코드 :