[Baekjoon] 14453. Hoof, Paper, Scissors (Silver) [S2]
📚 문제
https://www.acmicpc.net/problem/14453
N이 100000이라 O(n^2)으로 해결하려고 하면 시간초과가 난다.
누적합을 사용하여 O(n)으로 해결한다.
H가 바위, P가 보, S가 가위이다.
H, P, S의 누적합을 인덱스 별로 각각 2차원 배열에 담는다.
누적합을 첫번째 인덱스부터 탐색한다.
주먹 가위 보 중 2개를 뽑는다. 중복 없는 순열
(H, P), (H, S), (P, H), (P, S), (S, H), (S, P)
A와 B를 뽑았으면 A의[0, i]
누적합에 B의[i + 1 , n]
누적합을 더한다.
누적합을 구했으니 A는 확인한 인덱스 값을 더하면 되고 B는 [-1]인 끝 인덱스에서 현재 인덱스를 빼준다.
모든 인덱스에서 확인하면 O(n)으로 탐색할 수 있다.
📒 코드
import sys
input = sys.stdin.readline
n = int(input())
arr = [0] + [input().rstrip() for _ in range(n)]
prefix = [[0, 0, 0] for _ in range(n + 1)] # P, H, S
for i in range(1, n + 1):
if arr[i] == 'P':
prefix[i][0] += 1
elif arr[i] == 'H':
prefix[i][1] += 1
else:
prefix[i][2] += 1
for j in range(3):
prefix[i][j] += prefix[i - 1][j]
result = 0
for i in range(1, n + 1):
for j in range(3):
for k in range(3):
if j != k:
result = max(result, prefix[i][j] + prefix[-1][k] - prefix[i][k])
print(result)
🔍 결과
Author And Source
이 문제에 관하여([Baekjoon] 14453. Hoof, Paper, Scissors (Silver) [S2]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yunhlim/Baekjoon-14453.-Hoof-Paper-Scissors-Silver-S2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)