python 백준 27210 신을 모시는 사당

• https://www.acmicpc.net/problem/27210
• 원티드 주관 쇼미더코드에서 푼 문제

누적합 활용

• 시작점부터 왼쪽을 볼 경우 누적합에 +1, 오른쪽을 볼 경우 -1
• 시작점부터 (왼쪽을 바라보는 금색 돌상의 개수) - (오른쪽을 바라보는 금색 돌상의 개수)의 최대 지점 = 누적합에서 최대값
• 시작점부터 (오른쪽을 바라보는 금색 돌상의 개수) - (왼쪽을 바라보는 금색 돌상의 개수)의 최대 지점 = 누적합에서 최소값
• 그 두 지점의 차이가 최대한 깨달음의 차이

예시

• 2 2 1 1 1 2 1 1 1 이라고 가정
• arr : [0,-1,-2,-1,0,1,0,1,2,3]
• arr[0]은 시작점
• max(arr)지점은 arr[9]
• min(arr)지점은 arr[2]
• 2번째부터 시작하여 9번째까지 했을 경우 깨달음이 최대

import sys
input = sys.stdin.readline
def solution(arr:list[int])->int:
    cnt = [0]*(N+1)
    for i in range(1,N+1):
        if arr[i] == 1:
            cnt[i] = cnt[i-1] + 1
        else:
            cnt[i] = cnt[i-1] - 1
    minIdx,maxIdx = 0,0
    minValue,maxValue = 100001,-100001
    for i in range(N+1):
        value = cnt[i]
        if minValue > value:
            minIdx = i
            minValue = value
        if maxValue < value:
            maxIdx = i
            maxValue = value
    return abs(cnt[maxIdx]-cnt[minIdx])

N = int(input())
Target = [0]+list(map(int,input().split()))
ans = solution(Target)
print(ans)