글 읽기 - 1차원 배열의 특정 구간을 채우는 알고리즘이 있나요?

kbp0237 3년 전 0

예를들어 배열이 10칸이 선언이 되었다고 할 때,

인덱스가 0~3까진 -1로 채우고

인덱스가 2~6까진 2로 채운다고 할때

둘이 겹치는 구간인 2, 3 인덱스는 1로 채우고 이렇게 하고 싶은데 이런 경우 가장 효율적인 알고리즘이 뭔가요

결과 값 >>

-1 -1 1 1 2 2 2 0 0 0

sait2000 3년 전 1

채우는 구간을 미리 모두 알고 있을때는 전채 배열 길이에 비례하는 시간에 할 수 있습니다.

방법은 각 배열의 원소 대신 이웃한 두 항의 차이만 먼저 계산을 하는 겁니다. 그러면 연속한 구간에 값을 더해도 두 항의 차이는 두 군데이서만 바뀌기 때문에 금방 계산할 수 있습니다.

그 다음 마지막에 다시 더해주면 됩니다.

그런 거 말고 뭔가 실시간으로(?) 하는 방법도 있는데 그게 궁금하신 건 아닐 거 같네요.

palilo 3년 전 1

아래처럼 할 수 있는데 이걸 뭐라고 부르는지는 모르겠네요

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    // N: 구간 크기, M: 쿼리 개수

    vector<int> arr(N);
    vector<int> event(N + 1);
    for (int i = 0, l, r, w; i < M; ++i) {
        // [l,r] 구간에 +w   ==   l부터 끝까지 +w && r + 1부터 끝까지 -w
        cin >> l >> r >> w;
        event[l] += w;
        event[r + 1] -= w;
    }

    for (int i = 0, x = 0; i < N; ++i)
        arr[i] = x += event[i];

    for (int& x : arr)
        cout << x << ' ';
    return 0;
}

kbp0237 3년 전 0

@sait2000 @palilo 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1차원 배열의 특정 구간을 채우는 알고리즘이 있나요?

kbp0237 3년 전 0

sait2000 3년 전 1

palilo 3년 전 1

kbp0237 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말