[Algorithm🧬] 백준 18877 : Social Distancing

문제

처음에 생각한거 -> Memory Limit Excced

논리는 맞는데, 잔디 구간이 10^18 이라 grass 배열로 바꾸지 않고 생각해볼 필요가 있을 것 같음...

import sys

readl = sys.stdin.readline

# 최소 거리가 D 라고 했을 때 몇 마리의 소가 서있을 수 있는지.
def check(d):

    pos = grass[0]
    cow = 1

    for i in range(1, len(grass)):
        next_pos = grass[i]

        if (next_pos - pos) >= d:
            cow += 1
            pos = next_pos

    return cow


n, m = map(int, readl().split())
grasses = [list(map(int, readl().split())) for _ in range(m)]

grass = []

for start, end in grasses:
    for i in range(start, end + 1):
        grass.append(i)

# 가장 가까운 두 소 사이의 거리가 최대가 되도록.

left = 0
right = len(grass) - 1

sol = -1

while left <= right:
    mid = (left + right) // 2

    # 소가 많음 -> 거리를 늘려야 함.
    if check(mid) >= n:
        left = mid + 1
        sol = mid
    else:
        right = mid - 1


print(sol)

Time Limit Exceed

배열로 안만들고 풀었더니 memory 는 통과.
근데 시간이 문제이므로, 이거에 대한 정리가 필요.

import sys

readl = sys.stdin.readline

# 최소 거리가 D 라고 했을 때 몇 마리의 소가 서있을 수 있는지.
def check(d):

    pos = grasses[0][0]
    cow = 1

    for i in range(m):
        start, end = grasses[i]

        for next_pos in range(start, end + 1):
            if (next_pos - pos) >= d:
                cow += 1
                pos = next_pos

    return cow

def check(d):
    pos = grasses[0][0]
    cow = 1

    for i in range(m):
        start, end = grasses[i]

        # 다음 구간 시작 구간이 현재 마지막으로 소를 배치한 위치와 d 이상 차이나면
        # start 부터 다시 배치.
        if (start - pos) >= d:
            pos = start
            cow += 1

        while (pos + d) <= end:
            pos += d
            cow += 1

    return cow

계산 식 잘못됨.

이 아래의 반례 이 4개에서

d = 3 일 때 cow 개수를 비교해보자 뭔가 잘못 나오고 있음을 알 수 있음.

4 2
1 1
4 10

4 2
2 2
4 10

4 2
1 1
4 11

4 2
2 2
4 11

# 최소 거리가 D 라고 했을 때 몇 마리의 소가 서있을 수 있는지.
def check(d):
    # print('d=', d)
    pos = grasses[0][0]
    cow = 1

    for i in range(m):
        start, end = grasses[i]

        # 다음 구간 시작이 d 이상 떨어져있으면 다음 구간 시작으로 설정.
        if (start - pos) >= d:
            pos = start
            cow += 1
            # print(pos, cow)

        cow += (end - start) // d
        pos += ((end - start) // d) * d
        # print(pos, cow)

    return cow

정답

import sys

readl = sys.stdin.readline

def check(d):
    # print('d=', d)
    # 첫번째 구간에서 시작.
    pos = grasses[0][0]
    cow = 1

    for i in range(m):
        start, end = grasses[i]
		
        # 만약에 다음 구간이 d 거리 사이에 있다면 다음 구간부터 체크.
        if pos + d > end:
            continue

        # 다음 구간 시작이 d 이상 떨어져있으면 다음 구간 시작으로 설정.
        if (start - pos) >= d:
            pos = start
            # cow += 1
            # print(pos, cow)

        # 다음 구간 시작이 d 이상 떨어져있지 않으면서
        # 다음 구간이 엄청 작지 않으면 d 더해서 넘어감.
        elif pos + d <= end:
            pos += d
        

        # 예를 들어서
        cow += (end - pos) // d + 1
        pos += ((end - pos) // d) * d
        # print(pos, cow)

    return cow
    
 
 
n, m = map(int, readl().split())
grasses = [list(map(int, readl().split())) for _ in range(m)]


    # 가장 가까운 두 소 사이의 거리가 최대가 되도록.

left = 0
right = grasses[-1][1] - grasses[0][0]

sol = -1

while left <= right:
    mid = (left + right) // 2

    # 소가 많음 -> 거리를 늘려야 함.
    if check(mid) >= n:
        left = mid + 1
        sol = mid
    else:
        right = mid - 1


print(sol)

def check2(d):
    # 첫번째 소 배치
    idx = 0
    last = grasses[0][0]

    # 나머지 n - 1 마리의 소에 대해서
    for _ in range(n - 1):
        # 잔디 구간이 더 작으면 다음 잔디구간으로 넘어감.
        while idx < m and grasses[idx][1] < last + d:
            idx += 1
        
        # 위에서 나왔는데 잔디 구간이 남아있지 않아서 나온거면, 
        # 놓을 수 있는 cow 가 더 적은거니까 더 이상 검사할 필요 X
        if idx == m:
            return False
        
        # + d 한게 다음 잔디 구간 안에 있으면 + d 아니면 다음 잔디 구간 첫번째로 바꿈.
        last = grasses[idx][0] if grasses[idx][0] > last + d else last + d

    return True