[백준 11505] 구간 곱 구하기 Python 풀이

[백준 11505] 구간 곱 구하기 Python 풀이

📌 문제 분석

• 이 문제는 구간 곱을 구하는 문제로, 주어진 구간에 대한 곱을 빠르게 구하고 특정 인덱스의 값을 업데이트하는 작업을 요구합니다.
• 구간 곱을 효율적으로 계산하고 업데이트할 수 있는 방법으로 세그먼트 트리를 사용할 수 있습니다.
• 또한 결과를 구할 때마다 1000000007로 나눈 나머지를 출력해야 하므로, 이를 고려한 구현이 필요합니다.

🚨 시행착오

• 처음에는 구간 곱을 구하는 방식을 잘못 이해하고, 구간 곱을 구할 때마다 나머지 연산을 제대로 하지 않아서 틀린 결과를 얻었습니다.
• 세그먼트 트리를 사용하면서 구간 곱을 계산하고, 값이 갱신될 때마다 나머지 연산을 정확하게 적용하는 방식으로 수정했습니다.

처음 코드의 문제점

• 구간 곱을 계산할 때, 나머지 연산을 적절하게 적용하지 않아서 값이 매우 커지는 문제에 직면했습니다.
• 세그먼트 트리를 이용한 곱셈에서, 값을 나머지로 처리하는 부분이 누락되어 답이 잘못 나왔습니다.

어떻게 고쳤나요?

• 세그먼트 트리를 사용하여 구간 곱을 효율적으로 구하고, 값이 갱신될 때마다 나머지 연산을 적용하여 문제를 해결했습니다.
• 세그먼트 트리에서 각 노드는 자식 노드들의 곱으로 계산되며, 이를 빠르게 계산할 수 있도록 구현했습니다.

💡 해결 방안

import math

MOD = 1000000007

def set_tree(tree, idx):
    for i in range(idx, 1, -1):
        tree[i // 2] *= tree[i]
        tree[i // 2] %= MOD
    return

def update_tree(tree, idx, to):
    tree[idx] = to
    while idx > 1:
        idx = idx // 2
        tree[idx] = tree[idx * 2] * tree[idx * 2 + 1]
        tree[idx] %= MOD
    return

def find_tree(tree, start, end):
    results = []
    while start <= end:
        if start % 2 == 1:
            results.append(tree[start])
        if end % 2 == 0:
            results.append(tree[end])
        start = (start + 1) // 2
        end = (end - 1) // 2
    ans = 1
    for result in results:
        ans *= result
        ans %= MOD
    print(ans)
    return

n, m, k = map(int, input().split())
a = [int(input()) for _ in range(n)]
reqs = [list(map(int, input().split())) for _ in range(m + k)]

start_idx = 2 ** math.ceil(math.log2(n))
tree_size = start_idx * 2
tree = [1 for _ in range(10**7)]
tree[start_idx:tree_size] = a

set_tree(tree, start_idx + n)
for req in reqs:
    if req[0] == 1:
        update_tree(tree, req[1] + start_idx - 1, req[2])
    else:
        find_tree(tree, req[1] + start_idx - 1, req[2] + start_idx - 1)

🎯 이 문제의 핵심 포인트

1. 세그먼트 트리: 구간 곱을 효율적으로 계산하고 업데이트할 수 있는 자료구조.
2. 구간 곱의 계산: 트리를 사용하여 구간 곱을 O(log N) 시간에 계산할 수 있음.
3. 나머지 연산: 값이 매우 커질 수 있으므로, 모든 계산에서 MOD = 1000000007로 나눈 나머지를 구해야 함.
4. 트리의 구성과 인덱스 처리: 세그먼트 트리를 구현할 때, 트리의 크기와 인덱스를 정확히 계산하는 것이 중요함.

📝 예제로 이해하기

입력:
5 3 2
1
2
3
4
5
1 3 10
1 5 7
2 1 5
출력:
10
7

구체적인 설명:
- 처음에는 [1, 2, 3, 4, 5]로 시작합니다.
- 첫 번째 요청에서 3번 인덱스를 10으로 업데이트하면 트리는 [1, 2, 10, 4, 5]로 변합니다.
- 두 번째 요청에서는 5번 인덱스를 7로 업데이트하면 트리는 [1, 2, 10, 7, 5]로 변합니다.
- 세 번째 요청에서는 구간 곱 1~5를 구하는데, 1 * 2 * 10 * 7 * 5 = 700이지만, 나머지 연산을 고려하여 `700 % 1000000007 = 700`이 출력됩니다.

✨ 이번 문제를 통해 배운 점

1. 세그먼트 트리의 활용: 구간 곱을 효율적으로 구할 수 있는 방법을 배웠습니다.
2. 모듈러 연산: 값이 커지지 않도록 나머지 연산을 사용하는 것이 중요하다는 점을 배웠습니다.
3. 자료구조의 중요성: 큰 입력을 다루는 문제에서 세그먼트 트리와 같은 자료구조가 효율성을 높여 준다는 점을 배웠습니다.

🔍 코드 설명

• set_tree: 트리의 초기값을 설정하는 함수로, 리프 노드부터 부모 노드까지 값을 곱하고 나머지 연산을 진행합니다.
• update_tree: 주어진 인덱스에 값을 업데이트하고, 부모 노드까지 곱셈을 갱신합니다.
• find_tree: 구간 곱을 구하는 함수로, 주어진 구간에 대해 곱을 구하고 출력합니다.
• 모든 연산에서 값이 매우 커질 수 있으므로, 나머지 연산(MOD = 1000000007)을 적용하여 계산합니다.