[Python] 백준 2036번: 수열의 점수(시간복잡도 1등)

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

2036번: 수열의 점수

import sys
input = sys.stdin.readline


def getMaxScore(nums, N):
    if N == 1:
        return nums[0]

    score = 0

    # 음수
    for i in range(0, N-1, 2):
        cur, next = nums[i], nums[i+1]

        if cur < 0 and next < 0:
            score += cur * next
        else:
            if cur < 0 and next > 0:
                score += cur
            break

    # 전부 음수이면서 N이 3이상 홀수일 때의 반례
    if i+2 == N-1:
        if nums[N-1] < 0:
            score += nums[N-1]

    # 양수
    addPoint = 0
    for i in range(N-1, 0, -2):
        cur, next = nums[i], nums[i-1]

        if cur > 1 and next > 1:
            score += cur * next
        else:
            addPoint = i
            break

    # 나머지 양수들 더하기
    for i in range(addPoint, -1, -1):
        if nums[i] >= 1:
            score += nums[i]
        else:
            break

    return score


if __name__ == '__main__':
    N = int(input())
    nums = [int(input()) for _ in range(N)]

    nums.sort()

    maxScore = getMaxScore(nums, N)
    print(maxScore)

인덱스를 2씩 증가시키면서 음수에 대해서 도는데, 이 때의 조건은 i, i+1의 값이 모두 음수일 때이다. 그렇지 않을 경우 break로 반복문을 탈출하게 되는데, 이 때, i의 값이 음수, i+1의 값이 양수일 경우에는 음수인 i의 값을 점수에 더해준다.

다음으로 전부 음수이면서 N이 3이상 홀수일 때의 반례 처리를 해주는데, 가령

5

-2

-2

-3

-4

-5

와 같은 경우를 처리해주는 것이다.

 

다음은 양수 처리이다. 이것도 음수의 매커니즘과 매우 비슷한데, 다른 점은 1로 대소관계를 비교한다는 점과 addPoint라는 인덱스의 유무이다. 우선 1로 대소관계를 비교하는 이유는,

2

2

1

위 같은 경우일 때, 2*1이 아니라 2+1을 해주어야 되기 때문이다.

다음으로 addPoint는, 해당 인덱스부터 0이 나오기 전까지 모두 스코어에 더하겠다는 의미의 변수이다. for문 탈출 직전에 addPoint에 값을 넣어주고, 이후에 나머지 양수들을 처리해주면 끝난다.