[Python] 24838번 배열 구간합 놀이

 

 

https://www.acmicpc.net/problem/24838

24838번: 배열 구간합 놀이

---

 

23/08/04

 

 

내가 있는 스터디 그룹에서 이번 주 주간 문제로 다룬 문제 중 하나로, 구간 합을 적절히 이용한 재미있는 문제이다.

 

단점이라고 하면, 지문이 너무 길다는 것... 이 글에서는 지문을 전부 이해하고 있다는 가정 하에서 글을 쓸 것이다.

 

---

 

문제 접근 방식:

 

 

문제에서 주어진 예제를 잘 이해해 보자.

 

예제에서는 결론적으로, $1000$을 $2$번 더하고, $100$을 $1$번 더하고, $10$을 $0$번 더함으로써 $2100$이라는 최댓값이 나오게 되었다.

 

나는 최댓값이 나오게 될 때, 어떤 원소를 "몇 번" 더하게 되는지에 대해 주목했다. 즉, 어떤 원소의 "가중치"에 대해 생각해 봤다.

 

여기서 최댓값이 나오게 하려면 "가중치"가 제일 큰 것이 최대 원소에 매칭돼야 한다고 생각했다.

 

어떻게 보면 그리디적인 사고인데, 실제로 문제를 풀고 보니 그리디 알고리즘이 태그로 달려있었다.

 

어쨌든, 그 "가중치"는 어떻게 구할까?를 구현하는 데에 생각해 보니, 이는 충분히 누적합 알고리즘을 응용하면 구현할 수 있다고 생각했다.

 

근데, 구간이 여러 번(총 $m$번, $m$은 최대 $200,000$) 들어오니, 누적합 알고리즘 응용 중 하나인 imos 법을 써서 구현해 보자고 생각했다.

 

imos 법은 별거 없고, 누적 합 배열을 구현할 때 일일이 구간이 들어올 때마다 그 구간의 길이만큼 더해주는 것이 아니라 그 구간의 입장과 퇴장만 기록해 놓고 마지막에 누적합 배열의 길이(여기서는 $n$)만큼 처리를 해줌으로써 시간 복잡도를 줄이는 테크닉이다.

 

따라서 어떤 배열의 몇 번째 원소를 총 몇 번 더하는지 나타내는 배열, 다시 말하자면 가중치 배열, 즉, 누적합 배열을 $O(n + m)$의 시간복잡도로 구현할 수 있다.

 

근데 여기서 중요한 것은 방법의 수도 구해야 한다는 점인데, 문제에서 다행히도 배열 $A$의 원소들의 값들은 모두 다르다고 한 점 때문에 쉽게 구할 수 있다.

 

어차피 기본적인 아이디어는 "가중치"가 큰 곳에, 실제로 값이 큰 원소를 순서대로 매칭시키자,라는 아이디어이다.

 

근데 만약 배열 $A$의 원소들의 값들에 같은 값들이 있다고 해보자.

 

예를 들어, $A = [10, 10, 10, 2, 1, 1, 1]$이다. 그리고 가중치 배열은 $[1, 1, 1, 1, 2, 3, 3]$이다.

 

그렇다면, 최댓값은 $10$인데, 이 원소가 $3$개 있으므로 가중치 $2$에도 매칭될 수 있고 가중치 $3$에도 매칭될 수 있을 것이다.

 

그러면 계산하기 복잡해진다.

 

만약 배열 $A$의 원소들이 모두 다르다고 하면, (문제에서 주어진 상황임) 같은 원소 없이 크기가 잘 정렬되므로 그냥 매칭되는 경우의 수를 구하면 되는데, 이는 같은 가중치끼리의 길이의 계승의 곱들로 이루어져 있음을 알 수 있다.

 

예를 들어, $A = [10, 9, 8, 7, 6, 5, 4]$이고 가중치 배열이 위와 똑같다고 하면, 어차피 가중치 $3$짜리를 배정받을 원소는 $10$과 $9$, 두 개로 정해져 있음을 알 수 있다.

 

이 두 개의 순서를 바꾸는 경우의 수는 $2!$이다. 

 

마찬가지로, 가중치 $2$를 배정받을 원소는 $8$로 정해져 있고, 이 경우의 수는 $1$이다.

 

가중치 $1$을 배정받을 원소는 남은 $7, 6, 5, 4$이고, 이들을 나열하는 경우의 수는 $4!$이다.

 

따라서 이를 구현하면 된다.

 

나 같은 경우 같은 가중치가 얼마큼 있는지를 카운트해주는 $accum \ sum$이라는 딕셔너리를 선언하여 같은 가중치가 얼만큼 있는지를 세어주었다.

 

따라서 총 시간 복잡도 $O(T * ( n + m + n\mathrm{log}n ))$의 시간복잡도가 소요된다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 24838번 배열 구간합 놀이
# 누적 합, 구현, 정렬, imos
import sys
input = sys.stdin.readline
MOD = 100_000_000_7

T = int(input())  # 테스트 케이스의 수

def solve():
    n, m = map(int, input().rstrip().split())  # 배열의 원소 개수, 구간 개수
    A = sorted(map(int, input().rstrip().split()), reverse = True)
    imos = [0 for _ in range(n+1)]
    for _ in range(m):
        x, y = map(int, input().rstrip().split())
        imos[x-1] += 1
        imos[y] -= 1
    accum_sum = dict()
    weight = []
    now_val = imos[0]
    for i in range(1, n+1):
        if now_val in accum_sum:
            accum_sum[now_val] += 1
        else:
            accum_sum[now_val] = 1
        weight.append(now_val)
        now_val += imos[i]
    total_case = 1
    for key, value in accum_sum.items():
        for i in range(1, value+1):
            total_case *= i
            total_case %= MOD
    weight.sort(reverse = True)
    max_value = 0
    for i in range(n):
        max_value += A[i]*weight[i]
    return max_value, total_case

for _ in range(T):
    print(*solve())