[백준/파이썬] 27210 신을 모시는 사당 쇼미더코드 3회차

#문제링크

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

27210번: 신을 모시는 사당

#나의풀이

import sys

if __name__=="__main__":
    N = int(sys.stdin.readline())
    arr = list(map(int, sys.stdin.readline().split()))
    dp = [[0,0] for _ in range(N)]
    answer = 0

    if arr[0] == 1:
        dp[0][0] = 1
        dp[0][1] = -1
    else:
        dp[0][0] = -1
        dp[0][1] = 1

    for i in range(1 ,N):
        if arr[i] == 1:
            dp[i][0] = max(1, dp[i-1][0]+1)
            dp[i][1] = max(-1, dp[i-1][1]-1)
        else:
            dp[i][0] = max(-1, dp[i-1][0]-1)
            dp[i][1] = max(1, dp[i-1][1]+1)
    for i in dp:
        answer = max(answer, max(i))

    print(answer)

#해설

처음에 문제를 잘못 이해해서 왼쪽을 보고 있는 석상이 지식을 주고 오른쪽을 보는 석상이 지식을 뺏는줄 알고 풀다가 1시간동안 디버깅을 했다. 알고보니 두 석상을 뺀 절대값중 가장 큰 값을 찾는 문제

N = int(sys.stdin.readline())
    arr = list(map(int, sys.stdin.readline().split()))
    dp = [[0,0] for _ in range(N)]
    answer = 0

입력 부분으로 dp배열은 2차원으로 했다. [i][0]은 왼쪽을 본 석상의 dp값이 될것이고 [i][1]은 오른쪽을 보고 있는 석상의 dp로 설정했다.

    if arr[0] == 1:
        dp[0][0] = 1
        dp[0][1] = -1
    else:
        dp[0][0] = -1
        dp[0][1] = 1

0번째를 두고 초기값을 설정했다 첫번째수가 1이면 왼쪽dp가 1 오른쪽은 -1 지식을 얻고 있는것이고 반대일경우 반대로 점수를 얻게 된다.

    for i in range(1 ,N):
        if arr[i] == 1:
            dp[i][0] = max(1, dp[i-1][0]+1)
            dp[i][1] = max(-1, dp[i-1][1]-1)
        else:
            dp[i][0] = max(-1, dp[i-1][0]-1)
            dp[i][1] = max(1, dp[i-1][1]+1)

이후 2번째 수부터 돌면서 값을 확인한다.

현재값이 왼쪽을 보고 있다고 가정하면 현재부터 색칠한다고 하면 1점을 얻을수 있어 기본값이 1이고 이전 값과 연결한다면 dp[이전인덱스]값에 +1을 해준값이 된다. 이후 기본값과 연결된값을 비교해서 큰 값으로 설정한다.

    for i in dp:
        answer = max(answer, max(i))

    print(answer)

반복문을 돌면서 가장 큰 값을 찾고 출력한다.