[BOJ 27210, Python] 신을 모시는 사당 풀이

import sys
input = sys.stdin.readline

s_num = int(input())
s_list = list(map(int,input().split()))
m_list = []

before_s = s_list[0]
count = 0
if before_s == 1:
    count += 1
else:
    count -= 1


for i in range(1,s_num):
    if s_list[i] != before_s:
        before_s = s_list[i]
        m_list.append(count)
        count = 0
        if before_s == 1:
            count += 1
        else:
            count -= 1

    else:
        if s_list[i] == 1:
            count += 1
        else:
            count -= 1
m_list.append(count)

# print(m_list)

max_val = 0
min_val = 0

stack = 0

for statue in m_list:
    if(statue > 0):
        current_sum = max_val + stack + statue

        # 본인 값이 다 더한거보다 큰 경우
        if(statue >= current_sum):
            max_val = statue
            stack = 0

        # 이전 최댓값에 본인을 더하면(음수 포함해서) 더 커지는 경우
        elif (current_sum >= max_val):
            max_val = current_sum
            stack = 0

        # 최댓값보단 본인이 큰 경우
        elif (statue >= max_val):
            max_val = statue
            stack = 0
        
        else:
            stack += statue
    else:
        stack += statue

stack = 0

for statue in m_list:
    if(statue < 0):
        current_sum = min_val + stack + statue

        # 본인 값이 다 더한거보다 큰 경우
        if(statue <= current_sum):
            min_val = statue
            stack = 0

        # 이전 최댓값에 본인을 더하면(양수 포함해서) 더 작아지는 경우
        if (current_sum <= min_val):
            min_val = current_sum
            stack = 0

        # 최솟값보단 본인이 더 작은 경우
        elif (statue <= min_val):
            min_val = statue
            stack = 0
        
        else:
            stack += statue
    else:
        stack += statue


print(max(max_val,abs(min_val)))

 

사실 풀어놓고 코드 리뷰를 해도 어떻게 통과한건지 잘 모르겠는 코드이다.

 

우선 접근 방법은

1. 우선 수를 묶는다.

2. 묶은 수들로 매번 합을 비교해가며 가장 크게 나올 수 있는 합을 찾아간다

3. 가장 작게 나올 수 있는 합 또한 구한다.

4. 그 중 절댓값이 큰 값을 고르자

 

이런 방식으로 접근했는데

2번 과정을 어떻게 통과한건지 잘 모르겠다.

 

추후에 업데이트 예정!