[백준][누적합] 14453. Hoof, Paper, Scissors (Silver)

14453. Hoof, Paper, Scissors (Silver)

 

• 내 풀이
  • H, P, S를 각각 -> x= 0, 1, 2 로 두고
  • john이 각 값을 낼 때 bessi가 이길 수 있는 값은 y (= 1,2,0) 
    • 이건 x(= 0 ,1, 2)에 (x+1)%3 한 값
  • 이길 수 있는 값의 앞, 뒤 누적합을 구한다 = 해당 위치까지의 (0,1,2) 각각의 개수를 세는 것
    • prefix_count : 앞에서 부터 y 값의 개수를 센다 
    • suffix_count: 뒤에서 부터 y값의 개수를 센다
  • 이후, 각 위치에서 bessi가 내는 값을 변경한다고 했을 때, 이길 수 있는 총합을 계산
    • 2번 까지 하고 바꾸는 경우= 3~5번째는 다른 값 
      • 1~2번까지 한 것 중에 최대로 이길 수 있는 값 + 3~5(뒤에서부터는 1~3)에서 최대로 이길 수 있는 값
        • = prefix_count[2]+ suffix_count[3] 
      • 1번까지 한 것 중에 최대로 이길 수 있는 값 + 2~5(뒤에서부터는 1~4)에서 최대로 이길 수 있는 값
        • = prefix_count[1]+ suffix_count[4]

n = int(input())
john = [0]
for _ in range(n):
    x = input()
    if x == 'H':
        john.append(0)
    elif x == 'P':
        john.append(1)
    else:
        john.append(2)

# 이길 수 있는 값
john = [(x+1) % 3 for x in john]

# 이길 수 있는 값의 개수_앞에서 부터
prefix_count = [[0, 0, 0] for _ in range(n+1)]
for i in range(1, n+1):
    idx = john[i]

    prefix_count[i] = prefix_count[i-1][:]
    prefix_count[i][idx] += 1

# 이길 수 있는 값의 개수_뒤에서 부터
suffix_count = [[0, 0, 0] for _ in range(n+1)]
for i in range(n, 0, -1):
    idx = john[i]
    suffix_count[n-i+1] = suffix_count[n-i][:]
    suffix_count[n-i+1][idx] += 1

ans = 0
# 매 위치마다 이길 수 있는 경우의 합을 비교
for i in range(1, n):
    ans = max(ans, max(prefix_count[i])+max(suffix_count[n-i]))

print(ans)