[백준/24505] blobhyperthink (Python)

Problem : https://www.acmicpc.net/problem/24505

24505번: blobhyperthink

 

Difficulty : Platinum 4

 

Status : Solved

 

Time : 00:36:40

 

---

 

문제 설명

 

BOJ에 있는 문제를 본 블롭은 쉬는 시간에 이런 문제를 생각해 냈다.

길이가 N인 수열 A에서 다음 조건에 맞는 (i, j) 쌍의 개수를 구하자!

• i < j이고 Ai < Aj이다.

이 문제는 블롭에게 너무 쉬웠고, 블롭은 쌍의 원소 수를 세 개로 늘렸다. 하지만, 아직 이 문제는 블롭에게 너무 쉬웠고, 블롭은 쌍의 원소 수를 네 개로 늘렸다. ...

하지만, 아직 이 문제는 블롭에게 너무 쉬웠고, 블롭은 쌍의 원소 수를 열 개로 늘렸다. 하지만, 아직 이 문제는 블롭에게 너무 쉬웠고, 블롭은 쌍의 원소 수를 열한 개로 늘렸다. 이제 이 문제는 블롭에게 너무 어려워서 풀 수 없었다!

 

블롭을 위해 다음 조건을 만족하는 (i, j, k, l, m, o, p, q, r, s t) 쌍의 개수를 10^9+7로 나눈 나머지를 구하자.

• i < j < k < l < m < o < p < q < r < s < t 이고, Ai < Aj < Ak < Al < Am < Ao < Ap < Aq < Ar< As < At이다.

 

입력 및 출력

 

입력

 

첫째 줄에 수열의 길이 N이 주어진다.
둘째 줄에 수열의 원소를 나타내는 N개의 정수 A1, A2, ..., AN이 공백으로 구분되어 주어진다.

 

출력

 

첫째 줄에 조건에 맞는 쌍의 개수를 10^9+7로 나눈 나머지를 출력한다.

 

입력 예시

 

12
1 2 3 4 5 6 7 8 9 10 11 12

 

출력 예시

 

12

 

 

---

 

풀이

 

세그먼트 트리를 DP처럼 활용해보자! 가 포인트 되시겠다.

 

우리는 i번째 수 A[i]에 대해, [1, A[i]-1] 구간의 값을 참조하여야 한다. 이 중 임의의 값 A[j]에 대해, j < i 이고 A[j] < A[i]임이 자명하다. 따라서 A[j]구간의 길이 d인 쌍의 수가 있다면, A[i] 구간의 길이 d+1인 쌍의 수에 더해줄 수 있다.

 

문제는 이를 단순하게 처리하려면 O(N^2)의 시간복잡도가 요구된다. 따라서 2차원 세그먼트 트리를 사용하자. (2N x 11) 차원이 된다. i번째 수에 대해 처리하기 전에는 트리 내에 [1, i-1]까지의 값까지밖에 존재하지 않는다. 우리는 각 차원 d에 대해서, i번째 수에 대한 쌍을 더해줄 수 있다. 이는 [1, A[i]-1] 구간합과 동일하다. 따라서 각 길이 d에 대한 구간합, 그리고 그 구간합을 더해주는 업데이트를 실행함으로써 모든 N개의 값을 처리할 수 있다. 시간복잡도는 O(dNlogN)이고 이 문제에서는 d = 11이 된다.

 

 

풀이 코드

MOD = 10**9+7
N = int(input())
tree = [[0]*11 for _ in range(2*N)]

def update(idx, val, depth) :
  idx += N
  while idx :
    tree[idx][depth] = (tree[idx][depth]+val) % MOD
    idx //= 2

def search(left, right, depth) :
  left += N
  right += N
  res = 0
  while left <= right :
    if left % 2 :
      res += tree[left][depth]
      left += 1
    if right % 2 == 0 :
      res += tree[right][depth]
      right -= 1
    left //= 2
    right //= 2
  return res

nums = list(map(int, input().split()))
for i in range(N) :
  update(nums[i]-1, 1, 0)
  if nums[i] == 1 :
    continue
  for j in range(1, 11) :
    res = search(0, nums[i]-2, j-1)
    update(nums[i]-1, res, j)
print(tree[1][-1] % MOD)

풀이 완료!