[Lua] 백준 25419 정수를 끝까지 외치자

문제를 풀었으면 문제 풀이의 논리와 배울 점을 기록해 두는 게 좋은데, 최근에 귀찮아서 글을 너무 안 올린 거 같다.

 

팰린드롬 게임(24553번) 문제를 풀 때 코드는 애드 혹으로 냈지만 처음 떠올린 발상은 DP였는데,

이 아이디어를 기반으로 문제를 풀어보려고 게임 이론+다이나믹 프로그래밍 태그의 문제들을 뒤져보다 이 문제를 발견했다.

 

n,k=io.read("*n","*n")
ban={}
result={}
while 1 do --외칠 수 없는 숫자를 외치는 사람은 진다
    m=io.read("*n")
    if m==nil then break end
    ban[m]=1
    result[m]=false
end
if ban[n]==nil then result[n]=true else result[n]=false end --n을 외칠 수 있다면, n을 외칠 수 있는 사람은 무조건 이긴다
winner=0
function game(player,value)--player가 value라는 숫자를 외친다.
    if result[value]~=nil then return result[value] end
    if value>n then return false end
    local a=true
    for j=value+1,math.min(value+k,n) do
        if game((player+1)%2,j)==true and ban[j]==nil then a=false end
    end --내가 value라는 숫자를 외쳤을 때 상대가 이기는 경우가 하나라도 있다면 나는 진다. 상대는 최선의 선택을 하기 때문
    result[value]=a
    return a
end
for i=1,k do
    if game(1,i)==true then winner=1 end --1이 외치면 이기는 i가 하나라도 있다면 그 i를 외치면 되므로 승자는 1이다. 
end
io.write(winner)

 

누가 외치든 "이 숫자를 외치면 이긴다!" 인 숫자를 외쳐야만 이긴다.

result 배열은 value를 외쳤을 때 무조건 이기는 경우에만 True이다.