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

 

 

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

27210번: 신을 모시는 사당

 

 

 

원티드 쇼미더코드 3회차 문제 중 풀이에는 가장 짧은 시간이 들었지만, 코드가 가장 자신 없는 문제이다.

 

 

 

 

우선, 돌상이 왼쪽을 보고 있을 때는 누적값에 1을 더해주고, 돌상이 오른쪽을 보고 있을 때는 1을 빼주는 방식으로 누적값(curr 변수)을 계산했다.

 

예시를 하나 만들어보자면, 누적값을 아래와 같이 계산할 수 있다.

 

인덱스 : 0  1  2  3  4  5  6  7  8  9 10
방  향 :    왼 오 왼 왼 오 오 오 오 오 왼
누적값 : 0  1  0  1  2  1  0 -1 -2 -3 -2

 

이 누적값을 이용해서 a번 돌상부터 b번 돌상까지의 깨달음의 양을 구할 수 있다.

 

1번 돌상의 깨달음의 양은 abs(누적값[1] - 누적값[0])인 1이다. (왼)

2~4번 돌상의 깨달음의 양은 abs(누적값[4] - 누적값[1])인 1이다. (오왼왼 == 왼오왼왼 - 왼)

8~10번 돌상의 깨달음의 양은 abs(누적값[10] - 누적값[7])인 1이다. (오오왼 == 왼오왼왼오오오오왼 - 왼오왼왼오오오)

 

이걸 활용해서 깨달음의 최댓값도 구할 수 있다.

 

 

 

 

 

계산을 편하게 하기 위해 지금까지의 누적값의 최댓값(max_sum)과 최솟값(min_sum)도 계산해 준다.

 

인덱스 : 0  1  2  3  4  5  6  7  8  9 10
방  향 :    왼 오 왼 왼 오 오 오 오 오 왼
누적값 : 0  1  0  1  2  1  0 -1 -2 -3 -2
--------------------------------------------
최  대 : 0  1  1  1  2  2  2  2  2  2  2
최  소 : 0  1  0  0  0  0  0 -1 -2 -3 -3
--------------------------------------------
깨달음 :    0  1  1  2  1  2  3  4  5  4

 

지금 돌상을 포함시켜 금칠을 했을 때 깨달음의 최댓값은 abs(max_sum - curr), abs(curr - min_sum)의 최댓값이다.

 

예시에서 정답은 깨달음이 5가 되도록 5번 석상 ~ 9번 석상을 칠하는 경우이다...

 

 

 

 

N = int(input())
stones = list(map(int, input().split()))

curr, answer = 0, 0 # 지금까지 누적값 / 깨달음의 최댓값
min_sum, max_sum = 0, 0 # 지금까지 누적값의 최솟값, 최댓값

for stone in stones:
    if stone == 1: # 왼쪽보는 돌상
        curr += 1
    elif stone == 2: # 오른쪽 보는 돌상
        curr -= 1
	
    # 최대 깨달음 갱신
    answer = max(answer, abs(curr - min_sum))
    answer = max(answer, abs(max_sum - curr))
    
    # 최솟값, 최댓값 갱신
    min_sum = min(min_sum, curr)
    max_sum = max(max_sum, curr)

print(answer)

 

 

개념적으로는 누적합을 생각하고 풀었고, 누적합이라고 생각하는데... 이게 누적합이 아닐 수도 있고....

스택을 안 만들었다 뿐이지 비슷한 방법으로 스택 풀이도 가능할 것 같다. 아닐 수도 있고...