[백준] 31814. Sequence and Queries

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

문제요약

• 주어진 함수를 이해하고, 값을 출력
• 함수가 잘 와닿지는 않음
• 가능한 모든 경우의 ${i, j, k}$ 에 대해서 ${f(i,j,k)}$의 합을 출력
• ${s[i+t] <= s[j+t]}$ 이면 1인데, 모든 ${0<=t<k}$에 대해서

접근법

• 다 해보는 방법이 있겠는데 기본적으로 N^3을 넘어감.(모든 (i,j) 쌍에 대해서 (0~k)까지 계산)
• 잘 생각해보면 (i,j)쌍을 중복해서 살펴보는 경우도 있을 것이고, 활용할 수 있는 여지가 있음
• (i+t, j+t) 와 같이 (i,j)에서 t가 변하는 모양이기 때문에 i와 j의 간격을 활용해봄
• 일단 간격이 x인 모든 (i, j)쌍을 살펴본다고 가정함 (i<=j)
• i가 작은 것부터 큰 순서대로 살펴본다고 치면 결과를 모아볼 수 있을 것임(1 또는 0)
• 모아놓은 결과가 예를 들어 1 1 1 0 0 0 1 1 0 1 이라고 하면
• 앞에 "1 1 1"은 연속으로 3개가 가능하다는 의미임
• 우선 어떤 i,j에 대해서 ${f(i,j,2)}$ 를 만족할 것임
• ${f(i,j,1)}$ 을 만족하는 것은 2개가 있음
• 그리고 ${f(i,j,0)}$ 을 만족하는 것은 3개가 있음
• 만약에 연속으로 5개를 만족한다면?
  • ${f(i,j,4)}$ = 1
  • ${f(i,j,3)}$ = 2
  • ${f(i,j,2)}$ = 3
  • ${f(i,j,1)}$ = 4
  • ${f(i,j,0)}$ = 5
• 즉 연속으로 조건을 만족하는 길이를 이용하여 정답을 구해나갈 수 있음
• 배열을 뒤집어서도 동일하게 수행해줌(단 i==j인 경우는 앞에서 했으니 제외)