[Lua] 백준 1826 연료 채우기

 

 

문제집(1766번) 이후로 이런 일은 없을 줄 알았는데...  정해를 무시하고 내 방식대로 하겠다고 깝치다가 틀리거나 시간초과를 받은 게 너무 많아서 66번의 제출 끝에 맞았습니다!! 를 받았다.

 

(참고로, 정해 무시하고 내 방식대로 계속 코드 제출하다가 맞은 건 색종이 붙이기라는 문제 뿐이고, 이마저도 그냥 백트래킹만 한 게 아니라 경로 저장까지 해서 중복되는 경우를 없애서 확실히 맞을 거 같은 코드는 시간초과가 났고, 그 코드에서 함수 호출 횟수를 재서 특정 값을 초과하면 그냥 지금까지 계산한 결과를 반환하는 코드를 냈더니 932ms로 간신히 통과했다. 답에 해당하는 경우는 빨리 나오는데 모든 경우의 수를 다 계산하려면 많은 시간이 걸리는 문제였던 것으로 추정된다.

모든 경우의 수를 세려면 함수를 191836번 호출해야 하던 테스트 케이스도 실제로는 답이 15번만에 나왔었다.)

 

우선순위큐를 안 쓰고 정렬로만 하려다 시간초과가 나다가... 

 

일단 가지고 있는 연료를 다 써서 현재 위치를 바꾼 다음 이동한 범위 내에 있는 주유소들 중에서 연료를 채우고,

그렇게 해서 다음 주유소까지 가도록 하는 코드를 짰으나...

 

6

1 3

2 3

3 3

4 3

5 1 

17 3

20 4

 

이 반례 (내가 만들었고, 정해는 6이다.) 에서 문제가 생겼다. 모든 주유소에서 기름을 채워야 목적지에 도달할 수 있는데,

5번 주유소에 가려면 주유소 1~4에서 기름을 한 번만 채워도 되기에 기름을 한 번만 채웠고, 5번 주유소에서 6번 주유소에 갈 수 없어서 -1을 출력했던 것이다.

 

그래서 기준(코드에서는 변수 nextoil) 을 다음 주유소로 설정하고, 경우를 나눠서 nextoil을 어느 주유소로 할 지 구분하는 코드를 짜다가 엄청나게 많은 틀렸습니다를 받았고,

 

결국 다른 사람이 이 문제를 푼 로직만 읽고 구현을 해서 맞았습니다를 받았다.

 

(원래는 코드를 읽고 원리를 이해한 다음 코드를 그대로 다른 언어로 구현했는데, 소형기관차 문제를 시작으로 로직만 읽고 코드는 안 읽고 구현하는 게 가능해졌다.)

 

n=io.read("*n")
local dist,cnt
dist,cnt=0,0
oil={}
for i=1,n do a,b=io.read("*n","*n") oil[a]=b end
local l,p
l,p=io.read("*n","*n") --p:남은 연료량
oil[l]=0
queue={}
function inserting(idx)
    local j
    j=#queue+1
    queue[j]=idx
    while j>1  do
        if queue[j]>queue[j//2] then
            queue[j],queue[j//2]=queue[j//2],queue[j]
            j=j//2
        else
            break
        end
    end
end
function del()
  local point,ans=1,1
  if #queue>1 then
    ans,queue[1]=queue[1],table.remove(queue)
    while queue[point] do
      local a,b=queue[point*2],queue[point*2+1]
      if not a then break
      elseif not b then c=point*2
      elseif a>b then c=point*2
      elseif b then c=point*2+1
      else break
      end
      if queue[point]<queue[c] then
        queue[point],queue[c]=queue[c],queue[point]
        point=c
      else break
      end
    end
  else ans=table.remove(queue)
  end
  return ans
end
while dist<l do
    nextoil=l
    for i=dist+1,l do if oil[i]~=nil and nextoil==l then nextoil=i break end end
    for i=dist,dist+p do if oil[i]~=nil and oil[i]~=0 then inserting(oil[i]) oil[i]=nil end end
    while dist+p<nextoil and #queue>0 do
        p=p+del()
        cnt=cnt+1
    end
    p=p-nextoil+dist
    if p<0 then io.write(-1) os.exit() end
    dist=nextoil
    if dist>=l then io.write(cnt) os.exit() end
    if #queue==0 and dist+p<nextoil then io.write(-1) os.exit() end
end

 

 

(왜 티스토리 코드블럭에는 Lua랑 Rust가 없을까...?)

 

처음에는 dist값에다가 현재 연료량인 p값을 더하고 p를 0으로 만들었다가 nextoil(다음 주유소) 에서 채울 수 있는 만큼의 연료를 p값에 다시 할당하는 방식이었는데, 나중에는 nextoil을 dist,dist+p 사이에 있는 값으로 하고 nextoil과 dist의 차이를 p에서 빼주는 방식으로 했다. 후자만 맞았습니다!!! 를 받았다.