백준 5676번 [음주 코딩](C++)-yes6686- 티스토리

백준 문제 풀이: 5676 [음주 코딩]

---

문제 링크: https://www.acmicpc.net/problem/5676

문제 설명:

양수, 음수, 또는 0으로 이루어진 배열에 대해 주어진 구간의 곱의 부호를 구하거나, 특정 인덱스의 값을 변경하는 작업을 효율적으로 처리하는 문제입니다. 세그먼트 트리를 이용하여 O(log n) 시간 안에 구간 곱 계산과 값 변경을 처리합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[100001];
int t[400001];

int init(int n, int s, int e) {
    if (s == e) {
        return t[n] = arr[s];
    } else {
        return t[n] = init(2 * n, s, (s + e) / 2) * init(2 * n + 1, (s + e) / 2 + 1, e);
    }
}

int mul(int n, int s, int e, int l, int r) {
    if (r < s || l > e) return 1;
    if (l <= s && e <= r) return t[n];
    return mul(n * 2, s, (s + e) / 2, l, r) * mul(n * 2 + 1, (s + e) / 2 + 1, e, l, r);
}

int modify(int n, int s, int e, int i, long long int diff) {
    if (i < s || e < i) return t[n];
    if (s == e) {
        return t[n] = diff;
    }
    return t[n] = modify(2 * n, s, (s + e) / 2, i, diff) * modify(2 * n + 1, (s + e) / 2 + 1, e, i, diff);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, x;
    while (cin >> n >> m) {
        for (int i = 0; i < n; i++) {
            cin >> x;
            if (x > 0) arr[i] = 1;
            if (x == 0) arr[i] = 0;
            if (x < 0) arr[i] = -1;
        }
        init(1, 0, n - 1);

        char a;
        int b, c;
        for (int i = 0; i < m; i++) {
            cin >> a >> b >> c;
            if (a == 'P') {
                long long int k = mul(1, 0, n - 1, b - 1, c - 1);
                if (k == 0) cout << 0;
                if (k < 0) cout << '-';
                if (k > 0) cout << '+';
            } else if (a == 'C') {
                if (c > 0) arr[b - 1] = 1;
                if (c == 0) arr[b - 1] = 0;
                if (c < 0) arr[b - 1] = -1;

                modify(1, 0, n - 1, b - 1, arr[b - 1]);
            }
        }
        cout << '\n';
    }
}

---

코드 설명

• 핵심 알고리즘: 세그먼트 트리를 이용해 곱셈 구간의 부호를 효율적으로 계산합니다.
• 구현 세부사항:
  • init: 세그먼트 트리를 초기화하며 각 노드에 구간 곱의 부호를 저장합니다.
  • mul: 주어진 구간의 곱을 계산합니다. 반환값은 -1, 0, 또는 1로 표현됩니다.
  • modify: 배열의 특정 값 변경에 따라 세그먼트 트리를 갱신합니다.
  • 입력 값을 -1, 0, 1로 변환하여 곱셈 부호 계산을 단순화합니다.
• 시간 복잡도: O(log n) (각 쿼리에 대해)
  • 세그먼트 트리 초기화: O(n)
  • 곱셈 구간 쿼리와 값 갱신: O(log n)

---

결과

입력된 구간에 대해 곱셈 부호를 정확히 출력하며, 값 변경도 효율적으로 처리합니다. 세그먼트 트리를 활용하여 대규모 입력에서도 빠르게 동작합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!