[ 백준 ][ 골드1 ] 11505번 - 구간 곱 구하기 ( Python3 파이썬 )

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

11505번: 구간 곱 구하기

 

문제

---

코드

---

import sys
input = sys.stdin.readline

def merge(x,y):
    return x * y

def init(node,left,right):
    if left == right:
        stree[node] = arr[left]
        return stree[node]
    mid = (left+right)//2
    stree[node] = merge(init(node*2,left,mid),init(node*2+1,mid+1,right)) % 1000000007
    return stree[node]

def query(node,left,right,x,y):
    if x <= left and right <= y:
        return stree[node]
    if y < left or x > right:
        return 1
    mid = (left + right) // 2
    return merge(query(node * 2, left, mid, x, y), query(node * 2 + 1, mid + 1, right, x, y)) % 1000000007

def update(node,left,right,x,y):
    if left == right == x:
        stree[node] = y
        return stree[node]
    if x < left or x > right:
        return stree[node]
    mid = (left+right)//2
    stree[node] = merge(update(node*2,left,mid,x,y),update(node*2+1,mid+1,right,x,y)) % 1000000007
    return stree[node]

n,m,k = map(int,input().split())
arr = [int(input()) for _ in range(n)]
stree = [1] * (n*4+1)

init(1,0,n-1)

for _ in range(m+k):
    a,b,c = map(int,input().split())
    if a == 1:
        arr[b-1] = c
        update(1,0,n-1,b-1,c)
        continue
    print(query(1,0,n-1,b-1,c-1))

 

풀이

---

세그먼트 트리의 간단한 변형문제였지만 쉽지 않은 문제였다.

 

처음엔 n이 100만까지 올라가는 상황이었기에 세그먼트 트리보다는 펜윅 트리로 해결하려고 했다.

하지만 펜윅 트리로 코드를 짜보면 0이 들어가는 상황이 문제가 생기게 된다.

0이 없는 경우에는 상관이 없지만 어떤 값이 0으로 업데이트가 되어서 다른 값들도 모두 0으로 변하게 되면
다음번에 또 다른 값을 업데이트할 때 나누기의 분모가 0이 되어버리는 상황이 계속 발생하였다.

그래서 펜윅트리는 포기...내 1시간....

 

결국 세그먼트 트리로 돌아왔다.

세그먼트 트리로 구현하는 것은 기존으 덧셈 세그먼트 트리에서 더하기를 곱하기로 바꾸어주고 리턴값 몇개만 수정해주면 되어 간단했다.

근데 제출만 하면 2%, 4%에서 자꾸 시간초과가 나왔다.

 

이유는 값의 크기였다.

문제에서 나와있듯이 값이 너무 커질 수 있기 때문에 1000000007이라는 값으로 나눈 나머지를 정답으로 출력해야 한다.

난 최대한 코드를 간단히 하고자 하는 마음에 정답 출력할 때만 나머지를 구해줬는데 이렇게 하면 값이 이동하고 연산될 때 너무 많은 메모리와 시간을 잡아먹게 된다.

그래서 세그먼트 트리의 값을 바꾸어 줄때나 값이 이동할 때 항상 나눈 나머지를 사용하였더니 바로 통과되었다.

 

| 세그먼트 트리 |

• Init(node,left,right)
  • Init은 세그먼트 트리를 초기상태로 만들어 주는 역할을 담당한다.
  • 맨 처음 1,2,3,4,5라는 값들이 주어진다면 이 값들의 곱으로 이루어진 세그먼트 트리를 만든다.
  • left == right의 의미는 트리에서 단말노드를 방문한 것이고 세그먼트 트리에서 단말노드는 기본 원소 자체를 말한다.
• query(node,left,right,x,y)
  • x~y의 곱을 구하는 함수이다.
  • left,right는 현재 구간이고 x,y는 찾고자 하는 구간이다.
  • 현재 구간이 찾고자 하는 구간에 포함된다면 세그먼트 트리의 값 자체를 반환하고 현재 구간이 찾고자 하는 구간과 접점이 없다면 1을 반환한다.
  • 기존의 세그먼트 트리는 덧셈이었기에 0을 반환하지만 현재는 곱셈 세그먼트 트리이기 때문에 값이 강제로 0이 되는 것을 방지하기 위해서 1을 반환한다.
• update(node,left,right,x,y)
  • x번째 값을 y로 바꾸어 주는 함수이다.
  • left ==  right == x의 의미는 찾고자 하는 x번째 원소를 방문하였다는 의미이기에 세그먼트 트리의 값을 바꿔준다.
  • 현재 탐색중인 구간 (left,right)에 x가 포함되지 않으면 업데이트할 필요가 없기 때문에 현재 값 자체를 리턴해준다.