백준 11505 - 구간 곱 구하기 (Python3)

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

---

💡 해결방법

구간 곱을 다루는 세그먼트 트리를 구현해서 문제 해결

👀 풀이

• 세그먼트 트리로 초기화하는 메서드
• 기존 값을 변경해주는 메서드
• 입력된 구간 내의 곱을 반환하는 메서드

를 구현하여 정해진 쿼리를 처리한다.

특징으로는 기존 값을 원래는 내려가면서 업데이트를 했다면, 이번에는 말단 노드에서 시작해서 루트 노드까지 올라오며 update를 한다.

---

🧾코드

import sys
input = sys.stdin.readline

mod_value = 10**9+7

N, M, K = map(int, input().split())
arr = [int(input()) for _ in range(N)]
tree = [0] * (N*4)

def init(start, end, idx=1):
    if start == end:
        tree[idx] = arr[start]
        return tree[idx]
    mid = (start + end)//2
    tree[idx] = (init(start, mid, idx*2) * init(mid+1, end, idx*2+1)) % mod_value
    return tree[idx]

def interval(start, end, idx, left, right):
    if end < left or right < start:
        return 1
    if left <= start and end <= right:
        return tree[idx]
    
    mid = (start+end) // 2
    return (interval(start, mid, idx*2, left,right) * interval(mid+1, end, idx*2+1,left,right)) % mod_value

def update(start, end, idx, where, new):
    if end < where or where < start:
        return tree[idx]
    if start == end:
        tree[idx] = new
        return tree[idx]
    mid = (start + end) // 2
    tree[idx] = (update(start,mid,idx*2, where, new) * update(mid+1,end,idx*2+1, where, new)) % mod_value
    return tree[idx]

init(0, N-1)
repeat = M+K
for _ in range(repeat):
    a,b,c = map(int, input().split())
    if a == 1:
        update(0, N-1, 1, b-1, c)
        arr[b-1] = c
    else:
        print(interval(0, N-1, 1, b-1, c-1) % mod_value)

---

모듈러 연산

이 문제는 update 함수 구현에 힘을 많이 실어야 했다.

왜냐하면 풀이에 따라 모듈러 연산에 대해 잘 알아야 했기 때문이다.

 

나는 처음에는 트리의 루트부터 변경하려는 노드까지 쭉 내려가며, 노드의 정보를 업데이트 해주고 싶었다. 그래서 처음에는 아래 코드처럼 구현했었다.

# start : 0
# end : len(tree)-1
# idx : 트리의 노드, 1부터 시작
# where : 변경하려는 위치(arr 기준)
# origin : arr[where - 1] >> where은 1-based 이므로 -1 해줘야 함
# new : 변경하려는 값
def update(start, end, idx, where, origin, new):
    if end < where or where < start:
        return

    tree[idx] = (tree[idx]/origin * new) % mod_value

    if start == end:
    	tree[idx] = new
        return 

    mid = (start + end) //2
    update(start,mid,idx*2,where,origin, new)
    update(mid+1,end,idx*2+1,where,origin, new)

 

나는 tree[idx]는 항상 origin으로 나누어떨어진다고 판단했다. 왜냐하면 tree[idx]는 origin이 값으로 저장되어 있는 노드의 부모노드일테니 말이다.

그래서 tree[idx] / origin * new 를 하면 기존 값 대신에 새로운 값을 곱한 결과라고 생각하게 되었고, 이 결과에 mod를 하면 바른 값이 저장될 것이라고 판단한 것이다.

 

하지만 문제점이 있었다.

바로 모듈러 연산을 잘못 사용한 것이다. 모듈러 연산은 분배 법칙이 없다고 했고, 특히나 나눗셈 연산을 조심해야 했다. 나는 그것을 전혀 몰랐다.

 

동아리 분들에게 질문을 날린 덕에 알았다. 그건 바로 모듈러 역원(을 구하기 위해 페르마 소정리까지 알아야 함)을 구해야 했다. 수학 지식이 부족한 나여서 찾아봐도 이해가 잘 안 됐다. 대신에 이 아이디어가 틀린 아이디어는 아니란 것에 그래도 만족했다. 왜냐하면 이것 때문에 오늘 하루 2~3시간을 고민했기 때문이다.

 

그래서 chatGPT에게 부탁해서 아이디어를 반영한 코드를 받아봤다.

def mod_inverse(x, mod):
    return pow(x, mod - 2, mod)  # 페르마 소정리로 역원 계산

def update2(start, end, idx, where, new):
    if end < where or where < start:
        return
    
    # arr[where]을 제거하고, new를 곱함
    inverse = mod_inverse(arr[where], mod_value)
    tree[idx] = (tree[idx] * inverse % mod_value * new) % mod_value

    if start == end:
        arr[where] = new
        return

    mid = (start + end) // 2
    update2(start, mid, idx*2, where, new)
    update2(mid+1, end, idx*2+1, where, new)

이 코드로 제출했더니 결과는 성공이었다.

* 여기서 inverse는 1/arr[where] 과 동치라고 한다.

* pow 인자가 3개인 경우를 처음봤다. Python Docs에서 찾아보니, pow(a, exp, mod) 이다. 입력 받은 인자가 3개일 땐 a^exp mod mod를 리턴한다.

def update2(start, end, idx, where, new):
    if end < where or where < start:
        return
    
    tree[idx] = ((tree[idx] // arr[where]) % mod_value * new) % mod_value

    if start == end:
        arr[where] = new
        return

    mid = (start + end) // 2
    update2(start, mid, idx*2, where, new)
    update2(mid+1, end, idx*2+1, where, new)

그래서 빠르게 위 코드로 수정해서 제출 해봤지만 실패..