[누적합] 11660 구간 합 구하기 5, 3020 개똥벌레

3. 11660 구간 합 구하기 5

3.1. 문제유형

• 누적합

3.2. 풀이과정

1. 매 번 2중 for문을 계산할 시 시간초과가 발생할 것이다.
2. 따라서 미리 누적합을 계산해 놓고, 구간별로 뽑아 리턴한다.
3. 이 때, col 인덱스번호가 0이라면 종료값의 누적합을 덧셈한다.
4. 시작 인덱스가 0이 아니라면 종료값 - 시작값을 덧셈한다.
5. python 시간 초과 발생 -> pypy3로 통과

3.3. 소스코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

nums = [list(map(int, input().split())) for _ in range(n)]

for i in range(n):
    for j in range(1, n):
        nums[i][j] += nums[i][j-1]

for _ in range(k):
    xy = list(map(int, input().split()))
    sx, sy = xy[0]-1, xy[1]-1
    ex, ey = xy[2]-1, xy[3]-1

    total = 0

    for i in range(sx, ex+1):
        if sy == 0:
            total += nums[i][ey]
        else:
            total += (nums[i][ey]-nums[i][sy-1])
    print(total)

4. 3020 개똥벌레

4.1. 문제유형

• 누적합

4.2. 풀이과정

1. 석순은 아래, 종유석은 위에 위치한다.
2. 석순 높이는 그대로 사용하되, 종유석 높이는 (전체 - 종유석) 높이를 사용한다.
3. 석순과 종유석을 정렬 후, 이분탐색을 이용해 들어갈 높이별 장애물개수를 찾는다.
4. 핵심은 석순/종유석 탐색에는 이분탐색, 전체 높이는 순차탐색을 활용한다

4.3. 소스코드

import sys
input = sys.stdin.readline

def bs_search(height, cave):
    l, r = 0, len(cave)-1
    while l<=r:
        mid = (l+r)//2
        if cave[mid]<=height:
            l = mid+1
        else:
            r = mid-1

    return len(cave) - (r+1)

n, h = map(int, input().split())
top, bottom = [], []

for i in range(n):
    rock = int(input())
    if i%2 == 0:
        top.append(rock)
    else:
        bottom.append(rock)

top.sort()
bottom.sort()

rock_cnt, range_cnt = 1e10, 0

for i in range(1, h+1):
    top_cnt = bs_search(i-1, top)
    bottom_cnt = bs_search(h-i, bottom)
    cnt = top_cnt + bottom_cnt

    if cnt < rock_cnt:
        rock_cnt = cnt
        range_cnt = 1
    elif cnt == rock_cnt:
        range_cnt += 1
    else:
        pass
print(rock_cnt, range_cnt)