[백준 1744] 수 묶기

문제

www.acmicpc.net/problem/1744

1744번: 수 묶기

 

처음 작성한 코드

import sys

def get_max(arr):
    result = 0
    for i in range(0, len(arr), 2):
        if i < len(arr)-1:
            result += arr[i] * arr[i+1]
        else:
            result += arr[i]
    return result

N = int(sys.stdin.readline())
positive = [] #1초과
negative = [] #0이하, 0은 음수가 하나일 때, 곱해지는게 이득
one = [] #1은 곱해지지않고 더해져야 더 큰 수가 나옴

for i in range(N):
    tmp = int(sys.stdin.readline())
    if tmp <= 0: negative.append(tmp)
    elif tmp > 1: positive.append(tmp)
    else : one.append(tmp)

negative.sort() # 작은 것부터 나열해서 곱하면 제일 커지는 방향
positive.sort(reverse=True) # 큰 것부터 나열해야 제일 커지는 방향

result = get_max(negative) + get_max(positive) + sum(one) # 1은 모두 더해줘야 제일 커짐

print(result)

1. 입력받은 수를 0이하인 수(negative), 1초과인 수(positive), 1인 수들(one)으로 나눈다.
2. 음수는 작은거를 두개 곱하면 더 큰 수를 만들 수 있으니 그냥 sort를, 양수는 큰거 두개를 곱해야 더 큰 수를 만들 수 있으니 reverse=True 옵션을 줘서 정렬했다.
3. 1은 곱하는 것보다 더하는게 더 큰 수를 만들 수 있으니 sum(one)을 통해 입력받은 모든 1을 더해주도록 했다.

 

깨달은 점

• 이 문제는 그리디를 이용하여 푸는 문제라고 한다. 그리디 잘 모르겠다. 현재 상태에서 제일 좋은 걸 고르면 된다고 하는데 나는 그것도 모르고 현 상태 아니고 모든 상태에서 젤 좋은 값 구하려고 if문을 9138234개 정도 쓰면서 2시간을 날렸다 ㅋㅋ 재밌넹