백준 23327번 리그전 오브 레전드

🔒[문제 url]

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

🔑알고리즘

$a$번째 팀부터 $b$번째 팀까지 묶는다고 하자. 그렇다면 디비전의 재미는,
(첫번째 팀부터 $b$번째 팀을 묶은 디비전의 재미) - (첫번째 팀부터 $a$번째 팀을 묶은 디비전의 재미)가 된다.

• 따라서, prefixSum[i]에 첫번째 팀부터 $i$번째 팀을 묶은 디비전의 재미를 저장하자.

1. li 배열에 각 팀의 인기를 입력받는다.
2. li[i]가 첫번째 팀부터 $i$번째 팀까지의 인기의 합이 되도록 누적합을 구한다.
3. 그렇다면 prefixSum을 구하는 식은

prefixSum[i] = prefixSum[i-1] + li[i-1]*(li[i]-li[i-1]);

이 된다.

• $l$번째 팀부터 $r$번째 팀을 묶은 디비전의 재미는?
  • 위 식의 원리와 마찬가지로

  prefixSum[r] - prefixSum[l-1] - li[l-1]*(li[r]-li[l-1])

  이 된다.

🐾부분 코드

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
        cin >> li[i] , li[i] += li[i-1];
}

<입력 함수>
li 배열에 각 팀의 인기를 입력받으며, 누적합으로 전환한다.

//누적 합 구하기
for(int i = 1; i <= n; i++)
    prefixSum[i] = prefixSum[i-1] + li[i-1]*(li[i]-li[i-1]);

<누적 합 구하기>
예를 들어 각 팀의 인기가 1 2 3이라면
1. li = {1 , 2 , 3}
2. li = {1 , 3 , 6}
3. prefixSum = {0+0*(1-0) = 0 , 0+1*(3-1) = 2 , 2+3*(6-3) = 11}
이 된다.

🪄전체 코드

#include <iostream>
using namespace std;

typedef long long ll;
int n,q;
ll li[100001];
ll prefixSum[100001];

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
        cin >> li[i] , li[i] += li[i-1];
}


void SOLVE()
{
    //누적 합 구하기
    for(int i = 1; i <= n; i++)
        prefixSum[i] = prefixSum[i-1] + li[i-1]*(li[i]-li[i-1]);


    while(q--)
    {
        int l,r; cin >> l >> r;
        cout << prefixSum[r] - prefixSum[l-1] - li[l-1]*(li[r]-li[l-1]) << '\n';
    }

}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

수학적 사고는 정말 어려워...😭