백준 울려퍼져라 [32764] 파이썬(Python) 코드 + 해설

백준 32764 울려퍼져라 문제

 

백준 32774번 문제는 solved.ac기준 플레티넘 4입니다. 

 

월간 향유회의 운영진들은 각자 가지고 있는 공을 이용해 게임을 하려고 한다. 게임의 규칙과 목표는 다음과 같다:

• 각 운영진은 자신의 공을 모두 한 상자에 넣고 무작위로 섞는다.
• 상자에서 공을 하나씩 뽑으며, 같은 운영진의 공이 연속으로 뽑힐 때마다 해당 운영진은 1점을 얻는다.
• 게임은 여러 라운드로 진행되며, 각 라운드마다 참가하는 운영진의 범위가 주어진다.

이번 글에서는 모든 라운드가 끝난 후 각 운영진의 점수의 기댓값을 효율적으로 계산하는 방법을 소개한다.

1. 문제 이해하기

1.1 게임 규칙 요약

• 운영진 수: N명 (1≤N≤200,000)
• 각 운영진의 공의 수: A1​,A2​,…,AN​(1≤Ai​≤5,000)
• 라운드 수: Q개 (1≤Q≤200,000)
• 각 라운드의 참가자 범위: [li​,ri​]

1.2 목표

• 각 운영진이 얻는 점수의 기댓값 Ei를 계산한다.
• 기댓값은 분수 형태이며, 특정한 형식으로 출력해야 한다.

1.3 출력 형식

• 기댓값 Ei​가 기약분수 𝑝𝑖/𝑞𝑖일 때, 𝑝𝑖≡𝑞𝑖𝐸𝑖(mod10^9+7)을 만족하는 0≤pi​<10^9+7인 정수를 출력한다.

2. 알고리즘 설계

2.1 각 라운드에서 운영진의 기대 점수 계산

한 라운드에서:

• 총 공의 수 ​
• 운영진 i의 공의 수: S i ​ =A i ​ (단, 𝑙 𝑖 ≤ 𝑖 ≤ 𝑟 𝑖 인 경우)

운영진 i가 해당 라운드에서 얻는 기대 점수 Ei(round)는 다음과 같다:

​

​

2.2 전체 라운드에서의 기대 점수 합산

각 라운드의 기대 점수를 모두 합산하여 운영진별 총 기대 점수 Ei​를 계산한다.

2.3. 효율적인 계산을 위한 접근법

• 문제점: 각 라운드에서 모든 운영진에 대해 기대 점수를 계산하면 시간 복잡도가 O(NQ)로 너무 크다.
• 해결책: 누적합과 차분 배열을 활용하여 시간 복잡도를 O(N+Q)로 줄인다.

3. 코드 설계

3.1 필요한 계산 준비

3.1.1 공의 수 누적합 계산

• 목적: 특정 구간의 총 공의 수 T를 빠르게 계산하기 위함.
• 방법:

​

3.1.2 차분 배열을 이용한 구간 업데이트

• 목적: 각 운영진의 기대 점수에 대한 누적 기여도를 효율적으로 계산하기 위함.
• 방법:
  • 배열 delta를 초기화한다.
  • 각 라운드에서 [li,ri]구간에 대해 1/𝑇𝑖를 추가한다.

4. 백준 32764 울려퍼져라 문제 파이썬(python) 정답 코드

import sys
sys.setrecursionlimit(1 << 25)

MOD = 10 ** 9 + 7

def main():
    import sys
    input = sys.stdin.readline

    N, Q = map(int, input().split())
    A = list(map(int, input().split()))

    # 공의 수 누적합 계산
    prefix_A = [0] * (N + 1)
    for i in range(N):
        prefix_A[i + 1] = prefix_A[i] + A[i]

    delta = [0] * (N + 2)  # 차분 배열 초기화

    for _ in range(Q):
        l_i, r_i = map(int, input().split())
        l_i -= 1  # 0-based index로 변환

        T_i = prefix_A[r_i] - prefix_A[l_i]  # 해당 라운드의 총 공의 수
        if T_i == 0:
            continue  # 공이 없는 경우는 무시

        inv_T_i = pow(T_i, MOD - 2, MOD)  # 모듈러 역원 계산

        delta[l_i] = (delta[l_i] + inv_T_i) % MOD
        delta[r_i] = (delta[r_i] - inv_T_i + MOD) % MOD  # 음수 방지

    # 차분 배열로부터 각 운영진의 누적 기여도 계산
    S = [0] * N
    current = 0
    for i in range(N):
        current = (current + delta[i]) % MOD
        S[i] = current

    # 최종 기대 점수 계산
    E = [0] * N
    for i in range(N):
        Ai = A[i]
        if Ai >= 2:
            Ai_Ai1 = Ai * (Ai - 1) % MOD
            E[i] = Ai_Ai1 * S[i] % MOD
        else:
            E[i] = 0  # 공이 1개 이하인 경우 기대 점수는 0

    # 결과 출력
    print(' '.join(map(str, E)))

if __name__ == '__main__':
    main()

5. 백준 32764 울려퍼져라 문제 파이썬(python) 제출 결과

백준 32764 울려퍼져라 정답

 

도움이 되셨다면 공감과 댓글 부탁드립니다