288. 산책

1. Python

n, t = map(int, input().split())
now = []
speed = []
stack = []

for _ in range(n):
    a, b = map(int, input().split())
    now.append(a)
    speed.append(b)

for i in range(n):
    next = now[i]
    s = speed[i]

    if not stack:
        stack.append(next + (s * t))
        continue

    for time in range(t):
        next = next + s
        if stack[-1] >= next + s:
            s = speed[i - 1]

    stack.append(next)

print(len(set(stack)))
            


'''

5 3
0 1
1 2
2 3
3 2
6 1
3

'''

• 풀긴 풀었는데 아마 시간 복잡도에서 걸릴 것 같다.

• t가 10억이면 log의 속도가 아니면 t를 처리할 방도가 없다..

  • 1초에 대략 1억이면 t를 처리를 다르게 해야한다. 한 번에 곱해주던지 반복문에는 넣어서는 안될 것 같다.

• union - find로 도전해보기

  • 추월하면 부모의 속도로