2836

풀이1

1. 사람이 탈곳 내릴곳에 대한 인덱스를 각 배열로 만들어서 받는다.
2. 각 배열을 정렬한다.
3. 가장 끝 지점에서 타는 사람이 있는 인덱스까지 이동 거리를 더한다.
4. (현재 이동한 거리 - 내릴곳에 대한 인덱스 배열중 가장 작은 값)을 계산하여 더한다.
5. 다시 제일 먼거리에 있는 인덱스를 더해준다.
6. 현재 위치는 제일 먼거리에 있는 인덱스이므로 M - 현재위치를 마지막으로 더해주면 총 이동거리가 나온다.

n, m = map(int, input().split())
take = []
takeOff = []


for i in range(n):
  tk, tkO =map(int, input().split())

  take.append(tk)
  takeOff.append(tkO)


take.sort()
takeOff.sort()

res = take[n -1]
res += take[n-1] - takeOff[0]
res += takeOff[n-1] - takeOff[0]
res += m - takeOff[n-1] 

print(res)

오류
태우는 순간 다음 태우러 가는 인덱스와 데려다 줘야할 인덱스를 계산해서 최적 경로를 찾는것 같다. 저 코드는 계산x
손님을 태운순간, 데려다 준 순간 가야할 선택지는 두가지이다 다음 손님 vs 지금 손님의 도착 장소
그 중 이득인 걸 고르면 됨

풀이2

1. 사람이 탈곳 내릴곳에 대한 인덱스를 각 배열로 만들어서 받는다.
2. 현재 타고 있는 손님, 다음에 태울 손님의 인덱스를 저장하는 변수를 만든다.
3. 첫 손님을 먼저 태우고 다음 사람으로 갈지 데려다 줄지 이득인 거리를 계산하여 그 배열의 인덱스로 이동한다. 태운 사람과 데려다 준 인덱스는 각 배열에서 삭제
4. 마지막 남은 인덱스부터 m까지의 거리도 계산해서 더하면 끝

코드

n, m = map(int, input().split())
take = []
takeOff = []
res = 0

for i in range(n):
  tk, tkO =map(int, input().split())

  take.append(tk)
  takeOff.append(tkO)

tmp = 0
tk = 0
tko = 0

res = take[tk]
if (takeOff[tk] - tmp) > (take[tko] - tmp):
  tk += 1
  tmp = take[tk]
else:

오류
사람을 태우면 가야할 거리를 저장해놔서 현재 거리에서 다음에 태울 사람까지 거리와 저장된 가야할 거리중에서 가까운 곳이 있는지 비교해야 하는것 같다.

풀이3

1. 사람이 탈곳 내릴곳에 대한 인덱스를 각 배열로 만들어서 받는다.
2. 처음 사람을 받고 그 사람이 가야할 거리를 저장한다.
3. 현재 거리에서 다음손님과 가야할 거리를 비교하고 이득인 곳을 간다.
4. 매번 새로운 손님을 만날때마다 그 사람이 가야할 거리를 배열에 저장하고 한다.
5. 현재 거리에서 새로운 손님을 만나는거리와 가야할 거리를 저장한 배열안의 수 중에서 제일 짧은 거리를 비교하며 이득인 곳을 가는 것을 반복한다

코드

n, m = map(int, input().split())
take = []
takeOff = []
res = 0

for i in range(n):
  tk, tkO =map(int, input().split())

  take.append(tk)
  takeOff.append(tkO)

go = []
tmp = take[0]
nt = 1

res = take[0]
go.append(takeOff[0])

def findMinI():
  minI = 0
  minV = abs(go[0] - tmp)
  for i in range(len(go)):
    if minV > abs(go[i] - tmp):
      minV = abs(go[i] - tmp)
      minI = i
    elif minV == abs(go[i] - tmp):
      if go[i] < go[minI]:
        minI = i
  return minI 

while True:
  if nt == n:
    while len(go) != 0:
      minI = findMinI()
      res += abs(tmp - takeOff[minI])
      tmp = takeOff[minI]
      del go[minI]
    break

  minI = findMinI()
  minV = go[minI]
  if abs(tmp - minV) < abs(tmp - take[nt]):
    res += (tmp - takeOff[minI])
    tmp = takeOff[minI]
    del go[minI]
  else:
    res += abs(tmp - take[nt])
    go.append(takeOff[nt])
    tmp = take[nt]
    nt += 1

    
res += abs(tmp - m)
print(res)