10. 백준 코딩테스트 1744번 문제 python

이번에 풀 문제의 알고리즘은 Greedy Algorithm이다. 정답률은 27.3%이다.

https://www.acmicpc.net/problem/1744

1744번: 수 묶기

 

들어가기 전.

 

그리디(Greedy) 알고리즘은 최적의 해를 구하기 위해 사용되는 알고리즘 중 하나로, 여러 가지 경우 중 하나를 선택해야 할 상황이 올 때 그 순간에 최적인 것만 선택해 나가는 방식을 진행하여 최종적인 해답에 도달하는 알고리즘이다.

 

 

해결방법.

 

문제를 분석해보자.

받을 수 있는 값은 음수, 0 그리고 양수이다. 수를 두 개 묶어서 곱한 후 더하여 최대가 되는 값을 구하는 것이다. 부호에 따라 생각해보자.

 

• 두 수가 양수인 경우, 묶었을 때 최대가 되는 경우가 최적의 해답이다.
• 두 수가 음수인 경우 또한 절대값이 가장 큰 두 수를 묶었을 때 양수가 되어 최적의 해답이 된다.
• 묶었을 때 두 수의 부호가 다른 경우, 묶지 않는 것이 가장 좋은 방법이다. (부호가 다르면 곱하는 순간 커지므로)
• 0은 부호가 음수인 숫자에 묶어서 최대한 0으로 만든다.

이 4조건을 생각하며 문제를 해결해보자. 

 

#숫자의 총 길이
receive_length = int(input())
#양수리스트
receive_plus_list = []
#음수리스트
receive_minus_list = []
#0이 존재하는지 확인
is_contain_zero = False
result = 0

for i in range(0, receive_length):
    receive_input = int(input())
    #받은 값이 양수라면 양수리스트에 추가
    if receive_input > 0:
        receive_plus_list.append(receive_input)
    # 받은 값이 음수라면 음수리스트에 추가
    elif receive_input < 0:
        receive_minus_list.append(receive_input)
    #받은 값이 0이라면 True
    else:
        is_contain_zero = True
#절댓값이 가장 큰 숫자부터 묶기때문에 양수리스트는 내림차순으로 정렬.
receive_plus_list.sort(reverse = True)
receive_minus_list.sort()

#음수리스트에서 2개씩 묶어서 result에 더해준다.
for index in range(0, len(receive_minus_list)//2):
    result += receive_minus_list[index * 2] * receive_minus_list[(index * 2) + 1]
    
#음수리스트 길이가 홀수이면 두개씩 묶고 한개가 남으므로 더해주어야 한다.
#0이 존재하면 묶어서 0으로 처리가능하지만, 0이 없다면 어쩔수없이 빼주어야 한다.
if len(receive_minus_list) % 2 == 1:
    #0이 없다면 마지막 음수를 빼준다.
    if not is_contain_zero:
        #list[-1]은 마지막번째를 불러온다.
        result += receive_minus_list[-1]

#양수리스트 또한 더해준다. 다만, 양수리스트는 (1*1)보다 1+1이 더 큰 예외적인 경우가 발생한다.
#따라서 list[n]+list[n+1]과 list[n]*list[n+1] 중, 더 큰 것을 더해준다.
for index in range(0, len(receive_plus_list)//2):
    if receive_plus_list[index * 2] * receive_plus_list[(index * 2) + 1] > receive_plus_list[index * 2] + receive_plus_list[(index * 2) + 1]:
        result += receive_plus_list[index * 2] * receive_plus_list[(index * 2) + 1]
    else:
        result += receive_plus_list[index * 2] + receive_plus_list[(index * 2) + 1]

#양수리스트가 홀수라면 마지막 리스트를 더해준다.
if len(receive_plus_list) % 2 == 1:
    result += receive_plus_list[-1]

print(result)

리스트길이가 홀수인 경우를 생각하지않아서 틀렸다.