C. Diluc and Kaeya #724 Div.2

https://codeforces.com/contest/1536/problem/C
시간 2초, 메모리 256MB

input :

• t (1≤t≤1000)
• n (1≤n≤5⋅10^5)
• s ('D', 'K'로 이루어진 문자열)

output :

• For each test case, output n space separated integers. The i-th of these numbers should equal the answer for the prefix s1,s2,…,si.
  각 테스트 케이스에서 n개의 정수를 출력하시오. i번째의 숫자는 prefix들의 정답과 동일합니다.

조건 :

• They want to know the maximum number of pieces you can split the wood into such that the ratios of the number of occurrences of 'D' to the number of occurrences of 'K' in each chunk are the same.
  나무를 'D'의 출현 횟수, 'K'의 출현 횟수 비율에 맞게 나누었을 때 가장 많이 얻을 수 있는 경우의 수를 알기 원함.

• 'DDD' the ratio will be 3:0, for 'DKD' — 2:1, for 'DKK' — 1:2, and for 'KKKKDD' — 2:4. Note that the ratios of the latter two strings are equal to each other, but they are not equal to the ratios of the first two strings.
  예를 들어 'DDD'의 비율은 3:0이고, 'DKD'의 비율은 2:1, 'DKK'의 비율은 1:2, 'KKKKDD'의 비율은 2:4이다. 마지막 두개의 비율은 동일하다.

각 부분문자열을 봤을 때 그 비율에 대해서 모든 최대 공약수로 나눠서 가장 작은 비율로 만들 었을 때 이미 만들어진 적이 없다면 그렇게 구분 하려는 경우가 1개 밖에 없다고 볼수 있다.
내가 쓰면서도 무슨 말인가 싶긴 한데....

DKK 처럼 1 : 2 비율로 이미 한 번 나눈적이 있다면
DKKKKD의 경우는 2개로 나눌 수 있는 것이다. [DKK][KKD]

그러나 KKKKDD 의 경우에는 1개로 봐야 하는 것이다. prefix들로 비율을 저장 해 두기 때문에 동일한 비율로 나눈 적이 없어서 0에서 시작하기 때문에 1개를 카운팅 하는 것이다.

이를 x, y 좌표를 이용해서 설명 하는데 1 : 2, 2 : 4가 나온다면 이 둘은 원점과 연결을 했을 떄 동일한 선 위에 놓이게 된다. 그렇기 때문에 위와 같은 카운팅이 성립한다.

import sys
from collections import defaultdict
import math

t = int(sys.stdin.readline())
for i in range(t):
    n = int(sys.stdin.readline())
    data = sys.stdin.readline().rstrip()
    d = defaultdict(int)

    ans = []
    D, K = 0, 0

    for item in data:
        if item == 'D':
            D += 1
        if item == 'K':
            K += 1

        gcd = math.gcd(D, K)
        d[(D // gcd, K // gcd)] += 1
        ans.append(d[(D // gcd, K // gcd)])

    print(* ans)

최대 공약수를 통해 가장 작은 비율로 만들어 준다.
딕셔너리의 경우 튜플을 키로 이용할 수 있다.
그리고 배열의 값을 한 줄에 출력하려면 *배열이름을 사용하ㅣ자.