[BOJ 3002] 아날로그 다이얼(c++)

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

---

문제 개요

N개의 아날로그 다이얼(0~9까지 표시)이 일렬로 배치되어 있고, 각 다이얼의 숫자를 1씩 증가시킬 수 있는 버튼이 있습니다. (9는 1 증가시키면 0이 됨)

M번에 걸쳐 다음 작업을 반복합니다:

1. 범위 [A, B]를 선택
2. 해당 범위의 다이얼 숫자 합을 출력
3. 해당 범위의 모든 다이얼을 1씩 증가

주어진 초기 상태와 M개의 쿼리에 대해 각 쿼리마다 구간 합을 출력하는 문제입니다.

(1 ≤ N ≤ 250,000, 1 ≤ M ≤ 100,000)

---

문제 풀이

1시간 동안 접근법을 떠올리지 못하였는데 https://zzzz955.tistory.com/1113

[P2] 백준 3002번 아날로그 다이얼 C++ 세그먼트 트리, 느리게 갱신되는 세그먼트 트리

이 블로그에서 접근법을 확인한 후 풀이하였습니다.

 

 이 문제는 구간 합 쿼리와 구간 업데이트를 효율적으로 처리하기 위해 레이지 프로파게이션을 사용한 세그먼트 트리로 해결할 수 있습니다. 핵심 아이디어는 각 노드에 0~9까지 각 숫자의 개수를 저장하고, lazy 값으로 증가량을 관리하는 것입니다.

class node {
public:
    int sum;
    int cnt[10];
};

각 노드는 구간의 합(sum)과 각 숫자별 개수(cnt)를 저장합니다. 이를 통해 lazy 업데이트 시 숫자들을 회전시켜 새로운 합을 계산할 수 있습니다.

void update_lazy(int x, int s, int e) {
    if (lazy[x]) {
        seg[x].sum = 0;
        int tmp[10] = { 0, };
        for (int i = 0; i < 10; i++) {
            tmp[(i + lazy[x]) % 10] = seg[x].cnt[i];
        }
        for (int i = 0; i < 10; i++) {
            seg[x].cnt[i] = tmp[i];
            seg[x].sum += i * seg[x].cnt[i];
        }
        if(s != e){
            for (int i = x * 2; i <= x * 2 + 1; i++) {
                lazy[i] += lazy[x];
            }
        }
        lazy[x] = 0;
    }
}

lazy 업데이트 함수에서는 각 숫자를 lazy[x]만큼 회전시킵니다. 예를 들어, 3이 5번 증가하면 (3+5)%10 = 8이 됩니다. tmp 배열을 사용해 임시로 회전된 값을 저장한 후 적용합니다.

void update(int x, int s, int e, int l, int r) {
    update_lazy(x, s, e);
    if (r < s || e < l) return;
    if (l <= s && e <= r) {
        lazy[x]++;
        update_lazy(x, s, e);
        return;
    }
    int mid = s + (e - s) / 2;
    update(x * 2, s, mid, l, r);
    update(x * 2 + 1, mid + 1, e, l, r);
    update_parent(x);
}

업데이트 시에는 lazy 값을 1 증가시키고, 자식 노드들을 재귀적으로 업데이트한 후 부모 노드의 값을 갱신합니다.

int query(int x, int s, int e, int l, int r) {
    update_lazy(x, s, e);
    if (r < s || e < l) return 0;
    if (l <= s && e <= r) {
        return seg[x].sum;
    }
    int mid = s + (e - s) / 2;
    return query(x * 2, s, mid, l, r) + query(x * 2 + 1, mid + 1, e, l, r);
}

쿼리 함수는 먼저 lazy를 처리한 후 해당 구간의 합을 반환합니다.

시간 복잡도는 O(M log N)으로 효율적으로 처리할 수 있습니다.

---

코드

#include <iostream>
using namespace std;

class node {
public:
    int sum;
    int cnt[10];
};
int n, m;
string str;
node seg[250001 * 4];
int lazy[250001 * 4];

void update_parent(int x) {
    seg[x].sum = 0;
    for (int i = 0; i < 10; i++) {
        seg[x].cnt[i] = seg[x * 2].cnt[i] + seg[x * 2 + 1].cnt[i];
        seg[x].sum += seg[x].cnt[i] * i;
    }
}

void init(int x, int s, int e) {
    if (s == e) {
        seg[x].sum = str[s] - '0';
        seg[x].cnt[seg[x].sum]++;
        return;
    }
    int mid = s + (e - s) / 2;
    init(x * 2, s, mid);
    init(x * 2 + 1, mid + 1, e);
    update_parent(x);
}

void update_lazy(int x, int s, int e) {
    if (lazy[x]) {
        seg[x].sum = 0;
        int tmp[10] = { 0, };
        for (int i = 0; i < 10; i++) {
            tmp[(i + lazy[x]) % 10] = seg[x].cnt[i];
        }
        for (int i = 0; i < 10; i++) {
            seg[x].cnt[i] = tmp[i];
            seg[x].sum += i * seg[x].cnt[i];
        }
        if(s != e){
            for (int i = x * 2; i <= x * 2 + 1; i++) {
                lazy[i] += lazy[x];
            }
        }
        lazy[x] = 0;
    }
}

void update(int x, int s, int e, int l, int r) {
    update_lazy(x, s, e);
    if (r < s || e < l) return;
    if (l <= s && e <= r) {
        lazy[x]++;
        update_lazy(x, s, e);
        return;
    }
    int mid = s + (e - s) / 2;
    update(x * 2, s, mid, l, r);
    update(x * 2 + 1, mid + 1, e, l, r);
    update_parent(x);
}

int query(int x, int s, int e, int l, int r) {
    update_lazy(x, s, e);
    if (r < s || e < l) return 0;
    if (l <= s && e <= r) {
        return seg[x].sum;
    }
    int mid = s + (e - s) / 2;
    return query(x * 2, s, mid, l, r) + query(x * 2 + 1, mid + 1, e, l, r);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    cin >> str;
    init(1, 0, n - 1);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        int ret = query(1, 0, n - 1, x, y);
        cout << ret << '\n';
        update(1, 0, n - 1, x, y);
    }
    return 0;
}