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

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

27210번: 신을 모시는 사당

 

 

# 조건

• 신을 모시는 사당에는 신을 조각한 돌상 N개가 일렬로 놓여 있다. 각 돌상은 왼쪽 또는 오른쪽을 바라보고 서있다.
• 창영이는 연속한 몇 개의 돌상에 금칠을 하여 궁극의 깨달음을 얻고자 한다.
• 궁극의 깨달음을 얻기 위해서는 가능한 한 많은 금색 돌상들이 같은 방향을 바라보아야 한다. 방향이 다른 돌상은 깨달음에 치명적이다. 깨달음의 양은 아래와 같이 정의된다.
  • | (왼쪽을 바라보는 금색 돌상의 개수) - (오른쪽을 바라보는 금색 돌상의 개수) |

창영이는 궁극의 깨달음을 얻을 수 있을까?

 

입력

• 첫째 줄에 돌상의 개수 N이 주어진다.
• 둘째 줄에 돌상이 나열된 순서대로, 각 돌상이 바라보고 있는 방향이 주어진다.
• 입력의 편의상 왼쪽은 1, 오른쪽은 2라고 하자.

 

# 접근 방법

• dp를 이용하여 풀어주면 된다.
• 이 때, 왼쪽을 바라보는 동상 기준으로 1번
• 오른쪽을 바라보는 동상 기준으로 1번해주며
• 차례대로 더해준다.
• 이 때, 더하다가 음수가 되는 부분을 버려주면 된다.
• 예를들어 1 1 2 2 2 1 1 1 이라고 생각하면 아래와 같이 바꿔줄 수 있다.
• '1 1 -1 -1 -1 1 1 1' 순서대로 더해보면 1 -> 2 -> 1 -> 0 -> -1 -> 0 -> 1 -> 2이 된다. 이 때 음수가 나온 경우 음수인 구간을 애초에 무시해버리면 된다. 따라서 1 -> 2 -> 1 -> 0 -> -1(버림) -> 1 -> 2 -> 3 으로 마지막 3개를 구간으로 선택하는게 더 이득임을 알 수 있다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
  
N = int(input())  
statue = [*map(int, input().split())]  
  
total_value = 0  
cur_value = 0  
  
# 왼쪽을 바라보는 동상 기준  
for i in statue:  
    if i == 1:  
        cur_value += 1  
    else:  
        cur_value -= 1  
    if cur_value < 0:  
        cur_value = 0  
    total_value = max(total_value, cur_value)  
cur_value = 0  
# 오른쪽 바로보는 동상 기준  
for j in statue:  
    if j == 2:  
        cur_value += 1  
    else:  
        cur_value -= 1  
    if cur_value < 0:  
        cur_value = 0  
    total_value = max(total_value, cur_value)  
print(total_value)