백준 14453번 파이썬 문제풀이(Hoof, Paper, Scissors (Silver))

---

N이 10만이라 사실상 누적합으로 풀어야하는 문제이다. 

처음에 문제 접근 방식을 어떻게 해야하는지 계속고민하다 결국 힌트를 얻었다.

우선 P ,H , S를 냈을때 이기는 횟수를 구해 이를 누적합으로 저장해놓는다.

그후 인덱스를 다시돌면서 각각의 인덱스마다 다른걸 냈을때의 이기는 횟수를 구해 가장 큰값을 구해주는 식으로 했다.(즉, 지금이 P를 기준으로 3번째 인덱스라면 2번째까지 P가 이기는 횟수 + 3번째 인덱스부터 마지막까지 H로바꿧을때의 이기는 횟수) 와 같은식으로 각각의 6번의 모든 상황을 구해 가장 큰값을 구해주었다.

# H > S, S > P, P > H
import sys

input = sys.stdin.readline

N = int(input().rstrip())

H = [0] * (N + 1)
P = [0] * (N + 1)
S = [0] * (N + 1)

array = [0]
for i in range(N):
    array.append(input().rstrip())

for i in range(1, N + 1):

    if array[i] == 'H':
        H[i] = H[i - 1] + 1
        P[i] = P[i - 1]
        S[i] = S[i - 1]

    elif array[i] == 'P':
        H[i] = H[i - 1]
        P[i] = P[i - 1] + 1
        S[i] = S[i - 1]

    elif array[i] == 'S':
        H[i] = H[i - 1]
        P[i] = P[i - 1]
        S[i] = S[i - 1] + 1

result = 0
for i in range(1, N + 1):
    p_h = P[i - 1] + (H[N] - H[i - 1])
    p_s = P[i - 1] + (S[N] - S[i - 1])
    h_s = H[i - 1] + (S[N] - S[i - 1])
    h_p = H[i - 1] + (P[N] - P[i - 1])
    s_p = S[i - 1] + (P[N] - P[i - 1])
    s_h = S[i - 1] + (H[N] - H[i - 1])

    result = max(result, p_h, p_s, h_s, h_p, s_p, s_h)

print(result)