백준 11505: 구간 곱 구하기 [골드 Ⅰ/ Java]

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

11505번: 구간 곱 구하기

---

 

• 알고리즘 : 세그먼트 트리
• 풀이 날짜 : 2023.07.20.

 

 

< 풀이 설명 >

다음 문제와 연산 종류만 다를 뿐 동일한 문제이다.

[백준/Tree] - 백준 2042: 구간 합 구하기 [골드 Ⅰ/ Java]

 

 

 

입력 값 크기가 크고, 그 값들을 곱하는 연산을 하기 때문에,

연산 중간중간 정해진 값 (mod = 1,000,000,007) 으로 Modulo 연산 (나머지 연산) 을 해주어야 한다.

 

Modulo 연산은 나머지의 특징을 이용하는 연산이다.

이 연산이 타당한 이유는 간단하게 다음과 같이 설명할 수 있다.

A = 3 * q₁ + r₁
B = 3 * q₂ + r₂

A * B = 3 * Q + R  :R = r₁ * r₂

(A * B) % 3 = (3 * Q + R) % 3 = R % 3

 

 

 

하지만 주의할 점이 있다.

 

 

어떤 문제든 곱셈 및 나눗셈을 할 때 항상 DividedByZeroException 을 염두해두고 예외 처리를 잘 해주어야 한다.

 

 

또한 기존 배열의 값 변경시 처음에는 다음과 같이 변경된 차이만큼만 곱해주었는데,

private static void changeVal(int i, long new_val) {
    long origin = tree[i] % MOD;

    while (i > 0) {
        tree[i] = (tree[i] / origin * new_val) % MOD;
        i /= 2;
    }

}

 

부모 노드에는 mod로 나눈 나머지 값이 저장되어 있기 때문에 다음과 같은 오류가 생길 수 있다.

원래 값을 저장하지 않아서 옳은 답 복구가 어렵다.

A % mod = r₁
(r1 * k) % mod = r

if r₁ * k > mod:
   A % mod ≠ (r1 * k) % mod

 

 

 

구간 합 구하기 문제와 달리, 기존 배열 값을 이용하지 않고

자매 노드와 다시 곱하여 새로운 값을 부모 노드에 저장해 주어야 한다.

 

 

 

< 코드 >

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static final long MOD = 1_000_000_007;
    static long[] tree;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());   // 변경 횟수
        int k = Integer.parseInt(st.nextToken());   // 연산 횟수

        int lev = 0;
        while ((1 << lev) < n) lev++;
        int treeSize = (int) Math.pow(2, lev + 1);   // 3층 -> 2⁴ 
        int indexing = treeSize / 2 - 1;   // + 7 인덱싱

        tree = new long[treeSize];   // 0 ~ 2⁴ - 1 번 사용
        Arrays.fill(tree, 1);
        for (int i = indexing + 1; i <= indexing + n; i++)
            tree[i] = Long.parseLong(br.readLine());


        setTree(treeSize - 1);


        for (int i = 0; i < m + k; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());

            int s = Integer.parseInt(st.nextToken()) + indexing;
            long e = Long.parseLong(st.nextToken());


            if (a == 1) changeValZero(s, e);   // 변경
            else if (a == 2) sb.append(getTimes(s, (int) e + indexing)).append("\n");
            else break;

        }

        System.out.print(sb);
    }


    private static void changeValZero(int i, long new_val) {
        tree[i] = new_val;

        while (i > 0) {
            if (i % 2 == 1) tree[i / 2] = (tree[i] * tree[i - 1]) % MOD;
            else tree[i / 2] = (tree[i] * tree[i + 1]) % MOD;   // 왼쪽

            i /= 2;
        }

    }

    private static long getTimes(int s, int e) {
        long partTime = 1;

        while (s <= e) {
            if (s % 2 == 1) {   // 안쪽 선택 
                partTime = (partTime * tree[s]) % MOD;
                s++;
            }
            if (e % 2 == 0) {   // 안쪽 선택
                partTime = (partTime * tree[e]) % MOD;
                e--;
            }

            s /= 2;
            e /= 2;
        }

        return partTime;
    }


    private static void setTree(int i) {
        while (i != 1) {
            // MOD 값과 같아서 0이 되어도 어차피 곱하는 것이니 나머지가 0이란 뜻이니 상관 없음
            tree[i / 2] = (tree[i / 2] * tree[i]) % MOD;
            i--;
        }

    }

}