[Lua] 백준 27440 1로 만들기 3

간단한 BFS 문제이다. 사실 이 문제의 원본인 "1로 만들기" 는 다이나믹 프로그래밍 Well-known 문제인데,

이걸 BFS로 구현하는 게 더 빠르지 않을까 싶어서 구현해 보았다.

 

중간에 tbl이라는 테이블(루아의 자료 구조로, 파이썬의 딕셔너리와 비슷하다.) 에 메모이제이션을 하는 부분이 있는데,

BFS를 하면서 디버깅 출력을 해 보니 같은 리스트가 q에 계속 push되는 것이 확인되어(무한루프는 아니었지만 상당히 반복 횟수가 많아 시간을 많이 잡아먹는 듯 했다.) 메모이제이션을 하면서 이미 push한 값은 다시 push하지 않도록 했다.

(이렇게 하니 작동 속도가 상당히 빨라졌다.)

 

"1로 만들기" 문제는 BFS 방식을 활용해 시간을 줄이지 않으면 Lua로는 풀 수가 없어서 BFS를 활용해서 풀었다.

"1로 만들기" 코드를 조금 수정해서 "1로 만들기 3" 문제에 제출했을 때 "틀렸습니다"를 여러 번 받았는데, 그 이유는 t=math.floor(k//3) 부분을 t=math.floor(k/3)으로 잘못 써서 부동소수점 오류가 난 것이다.(Lua의 부동소수점 연산은 버전 5.4에서 추가되었다.)

 

어쨌든 그 부분을 고쳐주니 바로 정답이 나왔다.

 

n=io.read("*n")
q={}
q.first,q.last=1,1
q[1]={n,0}
tbl={}
function popFirst()
    value=q[q.first]
    if value==nil then value="False" end
    q[q.first]=nil
    q.first=q.first+1
    return value
end
function push(value)
    q.last=q.last+1
    if q[q.last]~=nil then q.last=q.last+1 end
    q[q.last]=value
end
while q.first<=q.last do
    local list
    list=popFirst()
    k=list[1]
    if k==3 or k==2 then cnt=list[2]+1 break end
    if k==1 then cnt=list[2] break end
    if k=="False" then break end
    if k%3==0 then
        t=math.floor(k//3)
        if tbl[t]==nil then tbl[t]=list[2]+1 push({t,list[2]+1}) end
    end
    if k%2==0 then
        t=math.floor(k//2)
        if tbl[t]==nil then tbl[t]=list[2]+1 push({t,list[2]+1}) end
    end
    if k>=4 then
        if tbl[k-1]==nil then tbl[k-1]=list[2]+1 push({k-1,list[2]+1}) end
    end
end
io.write(cnt)

중간에 있는 if문 몇 개는 사실 필요가 없다. 다만 시간을 조금이라도 줄이려고 넣은 코드이고 실제로 그 역할을 잘 한 거 같다.