본문 바로가기

카테고리 없음

[백준 9345번] 디지털 비디오 디스크(DVDs) (Python3)

import sys
input = sys.stdin.readline
mod = 10**9+7

def makeseg(start,end,x):
  if start==end:
    sseg[x] = mseg[x] = data[start]
  else:
    mid = (start+end)//2
    makeseg(start,mid,x*2); makeseg(mid+1,end,x*2+1)
    sseg[x] = sseg[x*2]+sseg[x*2+1]
    mseg[x] = mseg[x*2]*mseg[x*2+1]%mod

def updateseg(i,start,end,x):
  if start==end:
    sseg[x] = mseg[x] = data[start]
  else:
    mid = (start+end)//2
    if i <= mid:
      updateseg(i,start,mid,x*2)
    else:
      updateseg(i,mid+1,end,x*2+1)
    sseg[x] = sseg[x*2]+sseg[x*2+1]
    mseg[x] = mseg[x*2]*mseg[x*2+1]%mod

def sumseg(a,b,start,end,x,sseg,mseg):
  if a==start and b==end:
    return sseg[x],mseg[x]
  mid = (start+end)//2
  if b <= mid:
    return sumseg(a,b,start,mid,x*2,sseg,mseg)
  if a > mid:
    return sumseg(a,b,mid+1,end,x*2+1,sseg,mseg)
  s1,m1 = sumseg(a,mid,start,mid,x*2,sseg,mseg)
  s2,m2 = sumseg(mid+1,b,mid+1,end,x*2+1,sseg,mseg)
  return s1+s2,m1*m2%mod

for _ in range(int(input())):
  N,K = map(int,input().split())
  data = [i for i in range(1,N+1)]
  sseg = [0]*4*N; mseg = [0]*4*N
  
  makeseg(0,N-1,1)
  sseg1 = sseg[:]; mseg1 = mseg[:]
  
  for _ in range(K):
    q,a,b = map(int,input().split())
    if q:
      print("YES" if sumseg(a,b,0,N-1,1,sseg,mseg)==sumseg(a,b,0,N-1,1,sseg1,mseg1) else "NO")
    else:
      data[a],data[b] = data[b],data[a]
      updateseg(a,0,N-1,1); updateseg(b,0,N-1,1)

세그먼트 트리로 해결하였다.

문제의 의도와는 약간 다른 방식으로 해결하였다.

 

일단 풀이를 설명하면,

1. 1~N에 대해서 구간합에 대한 세그먼트 트리와 구간곱에 대한 세그먼트 트리를 만든다. (sseg = 구간합, mseg = 구간곱)

2. 갱신하지 않은 원래 세그먼트 트리를 저장해둔다. (sseg1,mseg1)

3. DVD 위치를 바꾸면 세그먼트 트리를 갱신한다.

4. 확인하는 경우 a,b일 때 a~b의 구간합과 구간곱이 원래의 값과 같다면 YES를, 아니라면 NO를 출력한다.

 

예를들어, 3~5 구간을 체크한다면, 구간합이 12 (=3+4+5), 구간곱이 60 (=3*4*5)가 나오면 3,4,5가 모두 있다고 판단하고 YES를 출력하는 것이다.

풀이가 통과한 것으로 봐서 생각했을 때는 테스트케이스에서는 반례가 없다고 판단되는데, 무조건 항상 성립하는지에 대한 증명은 하지 못했다.

 

 

원래 이 문제가 의도한 풀이는 구간곱, 구간합이 아니라 최대, 최소에 대한 세그먼트 트리를 이용하는 것이라고 한다. 비둘기집 원리에 의해서 a,b 구간의 최솟값이 a 최댓값이 b인 경우 a~b가 모두 있다고 판단할 수 있기 때문이다.

굉장히 참신한 아이디어였다.

 

 

오늘의 교훈) 비둘기집 원리를 풀이에 활용하자