[백준] 15977. 조화로운 행렬

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

접근법

• relabeling
  • 서로 다른 숫자로 구성되어있으므로 0부터 순차적으로 번호를 부여함
  • 1행 ~ 3행 모두 작업
  • 행이 두개만 주어지는 경우에는 3행을 임의로 만들어서 2행과 같다고 해도 동일한 효과가 나타남
• LIS
  • 1번 행을 정렬한 상태에서, (2번행, 3번행)으로 LIS를 만들어야하는데
  • 1번 행으로 인해 순서는 고정된 상태에서 (2번, 3번) 두 원소 모두 큰 것들을 판단해가면서 LIS를 만드는 부분이 어려움
  • pair 배열이 주어졌을때 LIS를 만드는 문제라고 생각
  • 2번행 원소 중 작은 것부터 접근한다면
    • k번째 2번행 원소로 끝나는 LIS를 구한다고 하면
    • 1 ~ k-1 번째로 구한 것들은 일단 2번행 원소는 k번째 보다 작을 것임
    • 이 상태에서 k 번째 2번행 원소보다 왼쪽에 있으면서 && k 번째 3번행 원소보다 작은 것들 중 가장 큰 값 + 1이 구하고자 하는 값임
    • 이를 위해 평방분할을 적용해봄
• 평방분할
  • $\sqrt{200000} = 448$
  • 가장 관심이 있는 3번행 원소와 LIS 값을 대상으로 함
  • 구간과 숫자를 평방분할하고 아래의 값을 지속적으로 업데이트함
    • 구간별 숫자 구간들이 갖고 있는 LIS의 누적 최대값
    • 구간별 숫자 구간들에 속하는 실제 숫자
    • 0 ~ 20만 위치별 3번행 원소의 표시
    • 3번행 원소당 구해놓은 LIS
  • 0 ~ x번째 위치까지 중에서 y보다 작은 것들중에 가장 큰 LIS를 구한다고 하면
    • x가 속한 구간의 바로 전까지 훑어보면서 + y가 속한 구간의 바로 전까지의 LIS의 최대값을 모음 : $\sqrt{n}$
      • 바로 전까지 하는 이유는 평방 분할에서 구간이 꽉 차지 않는 그 이유(구간 크기가 10 이라고 할때.. 13이면 13구간에 14, 15,... 속하는 현상)
    • 앞에서 구했을때 나머지로 남았던 것들을 모은다
      • x가 속한 구간에서 위치는 k보다 작고 숫자는 y보다 작은 것들
      • x의 바로 이전까지 구간중에서 y보다 작은 것들
      • 이들을 다 모아도 $\sqrt{n}$에 가능함
  • 그리고 할 일은 지금 구한 LIS를 업데이트
    • [위치구간][숫자구간]에 LIS 업데이트 + 누적 최대값 업데이트
    • [위치구간][숫자구간]에 k번째 행 숫자 업데이트
    • [위치]에 3번행 원소 표시
    • [3번행원소]에 LIS 업데이트

더 생각할 것

• 문제 굉장한 학생을 떠올렸음
• 다른 사람 코드는 수행시간이 짧았고
• 백준 알고리즘 분류에도 평방분할은 없는 것을 보니 더 적절한 접근법이 있나봄