[Lua] 백준 1949 우수 마을

그동안 알고리즘을 조금은 한 것 같다. 자력으로 푼 문제들이 여러 개 있지만 다 애드혹이라서 여기에는 올리지 않았다.

 

트리 DP를 여러 개 풀었더니 이제 트리 DP 문제는 자력으로 풀리는 것 같다. (라기엔 뉴스 전하기 문제도 자력으로 풀었던 걸 보면 그냥 내가 트리 DP랑 잘 맞나 보다.)

 

불(백준 4179번) 문제와 싸우느라 최근에는 많이 못 한 느낌이긴 하지만, 그래도 내 코드를 봐주는 사람이 있다는 걸 알게 되어서 기분이 좋다.

 

4179번은.. 데이터가 빡센 지 Lua로 계속 시간초과가 나길래 최적화를 열심히 하고(미로를 저장 안 했고, 재귀함수도 안 썼으며, 시간의 흐름을 기준으로 반복문을 돌려서 불이 붙은 시간을 무시하고 답을 구할 수 있었다.) 겨우겨우 996ms로 통과했는데, C++로 같은 알고리즘을 구현했더니(Lua에는 bool 배열을 선언하는 기능이 없지만 C++에는 있다. 큐에 들어가는 구조체를 제외하면 10^6 개의 bool값으로만 BFS를 돌렸다.) 60ms가 나왔다. 20ms대로 푼 사람들이 많은 걸 보면 내 코드가 최선은 아니었던 거 같다...

 

행, 열 1000개를 100개씩 쪼개서 2^10 * 10000 비트마스킹을 해볼까도 생각했는데 골4 문제에서 너무 뇌절하지 말자 라고 생각해서 관뒀다.

 

굳이 다른 문제 이야기를 하는 이유는, 딱히 쓸 게 없기 때문이다.

 

DP 구현 자체는 골5 수준 트리DP랑 다를 게 없고, 우수 마을로 지정되는 경우와 아닌 경우만 나눠서 DP를 짜면 되는 문제다. 난이도가 왜 골드2인지 잘 모르겠다...

 

물론 나는 머리를 조금 더 굴려서 코드를 짰지만, 20ms대로 통과한 걸 보니 그냥 대충 짰어도 상관없었던 것 같다.

 

n=io.read("*n")
value={}
for i=1,n do c=io.read("*n") value[i]={c,0} end
if n==1 then io.write(value[1][1]) os.exit() end
tree={}
for i=1,n-1 do
    a,b=io.read("*n","*n")
    if tree[a]==nil then tree[a]={} end
    if tree[b]==nil then tree[b]={} end
    table.insert(tree[a],b)
    table.insert(tree[b],a)
end
visited={}
function dp(node) 
    local yes,no=value[node][1],0
    for i=1,#tree[node] do
        local next=tree[node][i]
        if visited[next]==nil then
            visited[next]=1
            no=no+dp(next)
            yes=yes+value[next][2]
        end
    end
    value[node][1]=yes
    value[node][2]=no
    return math.max(yes,no)
end
visited[1]=1
io.write(dp(1))

 

(언젠가는 티스토리에서 Lua 코드블럭을 써먹을 수 있는 기능을 구현해 보고 싶다)

 

분명 트리DP 문제인데 dp배열은 없고 DFS 함수의 이름을 dp라고 해 놨다.

굳이 dp배열을 짜기가 귀찮아서 마을의 주민 수를 입력받은 value배열을 그냥 dp배열로 써먹었다.

따지자면 누적 합 슬라이딩 윈도우(?) 기법이라고 할 수 있겠다.

 

yes는 node마을을 우수 마을로 지정했을 때, no는 그렇지 않았을 때의 최댓값이다.

 

 

알고리즘 문제를 푸는 법에 대해 슬슬 눈이 트이는 느낌이다. 2학기 시작하기 전에 플래티넘을 찍는 게 목표다.

(나의 전공은 알고리즘과 관련이 없으므로, 학기 중에는 알고리즘을 안 할 것 같다. 어차피 방학 동안 알고리즘 외에도 코딩할 일이 많기도 하고...)