[백준] 27210.신을 모시는 사당

27210.신을 모시는 사당

 

 

• 내 풀이
  • 방향 1(왼쪽)을 기준/ 방향 2(오른쪽)을 기준으로 하는 최대 구간을 한 번씩 계산하여 큰 것 선택
  • 기준이 되는 방향을 x라고 할 때, 같은 방향이면 +1, 반대 방향이면 -1을 누적합처럼 처리
    • → 이 과정을 통해 깨달음의 양을 구함
  • 누적합을 유지하면서 최대 구간합을 계산
    → Kadane's algorithm (최대 부분 수열 합)과 유사한 방식

n = int(input())
nums = list(map(int, input().split()))

ans = 0

for x in [1, 2]:
    tmp = 0
    for num in nums:
        if tmp > 0:
            if num == x:
                tmp += 1
            else:
                tmp -= 1
        else:
            if num == x:
                tmp = 1
        ans = max(ans, tmp)

print(ans)

 

• 카데인 알고리즘

def kadane(arr):
    max_sum = float('-inf')
    current_sum = 0
    for num in arr:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

• 위와 같은 형식의 풀이

n = int(input())
nums = list(map(int, input().split()))

answer = 0

for x in [1, 2]:
    curr = 0
    max_val = 0
    for num in nums:
        score = 1 if num == x else -1
        curr = max(score, curr + score)
        max_val = max(max_val, curr)
    answer = max(answer, max_val)

print(answer)