[알고리즘/파이썬] 백준 알고리즘 1744번, 수 묶기

문제 출처 : www.acmicpc.net/problem/1744

1744번: 수 묶기

문제 정리

: 이번 문제는 주어진 수를 이용해 합할 때 최대 값을 구해서 출력하는 것이다. 수열 내에서 두개의 수를 묶을 수 있고, 묶은 수는 서로 곱한 후 다른 수와 더한다. 순서는 고려하지 않는다. 수열의 모든 수는 한 번만 묶일 수 있다.

: 예를 들어 {3, 9, 1, 2, 0} 의 수열이 들어오면 구할 수 있는 최대 합은 0 + 1 + 2  + ( 3 * 9 ) = 30 이다.

: 수열의 각 수는 -10000보다 크거나 같고, 10000보다 작거나 같은 정수이다.

문제 풀이

: 순서는 고려하지 않는다고 했으므로 각각 큰 수에서 부터 곱해서 더해주는 것을 기본으로,  1, 양수인 경우 2. 0인경우 3. 음수인 경우에 대해 생각해 볼 수 있다. 

1. 양수인 경우

: 수를 내림차순으로 정렬 한 후, 큰 수끼리 곱해서 각각 더해주면 된다.

: 단, 두 수 중 하나의 수가 1인 경우 곱하는 것 보다 더하는 것이 더 큰 수이므로 그 경우에는 곱하지 않는다.

: ( ex. 2 + 1 > 2 * 1 )

2. 0인 경우

: 양수에 곱해질 때에는 무조건 값이 낮아지므로, 음수에 곱해질 때에만 곱셈 연산을 하고, 이외에는 그냥 합해준다.

3. 음수인 경우

: 두 음수를 곱하면 양수가 되므로, 수를 오름차순으로 정렬한 후 작은 수 끼리 곱해서 각각 더해준다.

: 이 때 오름차순 정렬을 하는 이유는 음수는 절댓값이 클 수록 작은 수이기 때문이다.

: 음수 * 0 의 경우 0을 곱해주는 것이 최댓값을 얻을 수 있는 방법이며, 음수와 양수가 붙어있는 경우 덧셈 연산을 해주는 것이 최댓값을 얻는 방법이다.

 

풀이에 따라서,

양수 배열과 음수, 0을 담는 배열을 따로 만든 후 기준에 따른 연산을 해주었다.

코드

pos_nums = []
neg_nums = []
result = 0
for _ in range(N) :
	num = int(input())
	if num > 0 :
		pos_nums.append(num)
	else : 
		neg_nums.append(num)

pos_nums.sort(reverse = True)
neg_nums.sort()

result = 0

for i in range(len(pos_nums)) :
	if i % 2 == 0 and i + 1 < len(pos_nums) :
		if pos_nums[i] == 1 or pos_nums[i + 1] == 1 :
			result += (pos_nums[i] + pos_nums[i + 1])
		else :
			result += (pos_nums[i] * pos_nums[i + 1])
	elif i == len(pos_nums) - 1 and len(pos_nums) % 2 == 1 :
		result += pos_nums[i]

for i in range(len(neg_nums)) :
	if i % 2 == 0 and i + 1 < len(neg_nums) :
		result += (neg_nums[i] * neg_nums[i + 1])
	elif i == len(neg_nums) - 1  and len(neg_nums) % 2 == 1 :
		result += neg_nums[i]

print(result)

+ ) 풀다가 느낀점

- 뭔가 나눗셈 연산 말고도 풀 수 있는 방법이 있을 것 같은데 잘 모르겠다.

- 이번 문제의 경우 처음에 1 에 관해서 생각을 못하다가 테스트 케이스를 작성하면서 예외 처리가 필요하다는 것을 깨달았다.

- 문제를 풀기전에 좀 더 생각해 보는 시간을 가져야겠다.