Python/Greedy BOJ-1744 수묶기

Posted on | In

[Python/Greedy] BOJ-1744 수묶기

📌문제링크 kyoung-jnn 님의 플이

*풀이링크 들어가셔서 보시면 됩니다.

수열을 묶어 최대 합을 구하면된다. 전형적인 그리디 알고리즘을 활용하면 되는 문제다.
양수는 내림차순, 음수는 오름차순으로 정렬해서 차례로 곱하거나 더해주면된다.
무조건 1의 경우 더하기를 해야하는 점이 포인트다.

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import sys
input = sys.stdin.readline
if __name__ == '__main__' :
    N = int(input())
    pos = []; neg=[]
    for _ in range(N) :
        tmp = int(input())
        if tmp > 0 : pos.append(tmp)
        else: neg.append(tmp)
    neg = sorted(neg)
    pos = sorted(pos, reverse=True)
    result=0    
    if len(neg) % 2 == 0 :
        for i in range(0,len(neg),2):
            result += neg[i] * neg[i+1]
    else :
        for i in range(0,len(neg)-1,2):
            result += neg[i] * neg[i+1]
        result += neg[len(neg)-1] # 마지막 숫자 더해주기 
    
    if len(pos) % 2 == 0 :
        for i in range(0,len(pos),2):
            if pos[i]==1 or pos[i+1]==1 : # 1인 경우 더하기
                result += (pos[i]+pos[i+1])
            else :
                result += pos[i] * pos[i+1]
    else :
        for i in range(0,len(pos)-1,2):
            if pos[i]==1 or pos[i+1]==1 : # 1인 경우 더하기
                result += (pos[i]+pos[i+1])
            else :
                result += pos[i] * pos[i+1]
        result += pos[len(pos)-1] # 마지막 숫자 더해주기 
    print(result)