[백준] 27210번 - 신을 모시는 사당 (Python, 파이썬)

문제

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

27210번: 신을 모시는 사당

 

접근 방법

연속합을 구하는 방식의 DP로 푸는 방식이 정석으로 보이나, 여기서는 분할정복 알고리즘을 이용하여 풀이하였다.

돌상을 절반씩 분할해나간후, 이들을 합치는 과정에서 최댓값이 왼쪽/오른쪽/중앙포함 구역에서 나오는 경우 세 경우를 모두 확인하고, 이들중 최댓값을 선택하는 방식으로 문제를 풀었다.

 

코드

import sys

def getMidScore(arr, mid): # 가운데를 반드시 포함했을 때 최대점수 확인
    leftMinusRightTotal = 0
    rightMinusLeftTotal = 0
    
    leftMinusRight = 0
    rightMinusLeft = 0
    currentLeft = 0
    currentRight = 0
    for i in range(mid - 1, -1, -1): # 왼쪽으로 확인
        if arr[i] == 1:
            currentLeft += 1
        elif arr[i] == 2:
            currentRight += 1
            
        if leftMinusRight < currentLeft - currentRight:
            leftMinusRight = currentLeft - currentRight
        if rightMinusLeft < currentRight - currentLeft:
            rightMinusLeft = currentRight - currentLeft
            
    leftMinusRightTotal += leftMinusRight
    rightMinusLeftTotal += rightMinusLeft
    
    leftMinusRight = 0
    rightMinusLeft = 0
    currentLeft = 0
    currentRight = 0
    for i in range(mid, len(arr)): # 오른쪽으로 확인
        if arr[i] == 1:
            currentLeft += 1
        elif arr[i] == 2:
            currentRight += 1
            
        if leftMinusRight < currentLeft - currentRight:
            leftMinusRight = currentLeft - currentRight
        if rightMinusLeft < currentRight - currentLeft:
            rightMinusLeft = currentRight - currentLeft
            
    leftMinusRightTotal += leftMinusRight
    rightMinusLeftTotal += rightMinusLeft
    
    return max(leftMinusRightTotal, rightMinusLeftTotal)
        

def getMaxScore(arr):
    if len(arr) == 0:
        return 0
    elif len(arr) == 1:
        return 1
    
    mid = len(arr) // 2
    leftMax = getMaxScore(arr[:mid])
    rightMax = getMaxScore(arr[mid:])
    midMax = getMidScore(arr, mid)
    
    return max(leftMax, rightMax, midMax)

N = int(sys.stdin.readline().rstrip())
arr = list(map(int, sys.stdin.readline().rstrip().split()))

print(getMaxScore(arr))