[BOJ][Python]2579번 풀이

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

n = int(input())
t = [0 for _ in range(301)]
s = [0 for _ in range(301)]
for i in range(1,n+1):
    s[i]=int(input())
t[1],t[2] = s[1],s[1]+s[2]
for i in range(3,n+1):
    t[i] = max(s[i]+s[i-1]+t[i-3],s[i]+t[i-2])
print(t[n])

저는 도저히 이걸 어떻게 3칸은 안밟도록 할 수 있나 계속 고민했는데 생각 보다 간단하게 구현할 수 있다는 것에 충격을 받았습니다. 일단 해당 문제는 dp이며 점화식을 만들기 위해서 직접 써보거나 고민을 해보신 분들은 dp라는 사실을 바로 눈치채셨을겁니다. dp라는 걸 알았다면 언제부터, 무엇이 점화식인가를 찾아야겠죠. 사실상 n이 1,2 일 때는 무조건 고정이기 때문에(계단의 값은 자연수라는 조건이 있기 때문에 많이 밟을수록 점수가 높음) 식은 3부터 의미가 생기는구나 라고 아시면 될 것 같습니다.

 

사실 dp를 풀다보면 처음에는 아 이걸 어떻게 최적의 해를 구하지라는 생각이 먼저 드는데요. 하다보면 어차피 최적의 해가 존재하기 때문에 점화식만 구축하면 굳이 무엇이 최적의 해가 되는지 안되는지를 따질 필요가 없습니다. 저희는 답이 없는 것에서 답을 찾아내는 것이 아니라 이미 존재하는 답으로 가는 길만 찾으면 되니까요. 그럼 위에서 말했듯이 3부터 점화식에 의미가 생김을 알아차렸으니 당연히 반복문은 3부터 시작을 하면 될 것이구요. 해당 문제는 마지막칸은 무조건 밟아야 하기 때문에 한 번에 3칸을 밟지 않도록 하기 위해서는 점화식에서 일부러 피할 칸을 정해서 식을 짜주면 됩니다. 예를 들어서 주어진 n에 대해서 최댓값을 구한다면 n은 무조건 밟아야 하니 고정이고 n-1을 밟을지 n-2를 밟을지가 이제 선택사항이 되겠죠(3칸 연속은 안되니까 n-1과 n-2 둘 중 하나는 무조건 포기해야합니다). 그 아래는 의미 없습니다. 어차피 우리가 식을 제대로 세웠다면 그 보다 아래 칸에 대해서는 무조건 정답이라는 뜻이니까요. 따라서 값이 구해지는 과정은 각각,

n + n-2 + ...

n + n-1+ n-3+...

이 되겠죠(n-2일 때 뒤에 n-3이 붙지 않는 것은 n-3, n-4가 이미 밟았을 가능성이 있기 때문입니다. 하지만 n-1의 경우 n-4를 이미 밟았다한들 상관없죠 n-2가 이미 띄워져 있으니). 그 아래는 우리가 너무나도 완벽하게 잘 구해놨다고 믿고 맏기시면 되는 겁니다. 따라서 이 부분을 식으로 구현하면,

for i in range(3,n+1):

    t[i] = max(s[i]+s[i-1]+t[i-3],s[i]+t[i-2])

이렇게 되는 것입니다. 다시 말하지만 n-1을 비울 것인지, n-2를 비울 것인지만 우리는 정해주면 됩니다. 이 식이 완벽하다면 그 아래 값들은 이미 최적의 해가 구해져 있다는 뜻이니까요.

 

설명을 좀 더 깔끔하게 해드리고 싶은데 오늘의 설명은 약간 감각에 의존하는 설명이 되어서 조금 아쉽습니다. 제가 전문 강사라면 훨씬 잘 가르쳐 드릴 수도 있을 것 같은데 오늘 설명같은 경우는 dp를 많이 풀어봤다는 한에서 '식이 제대로 세워졌다면 이전 값들은 이미 다 맞기 때문에 믿고 사용해도 된다' 의 태도를 이미 익히신 분들만 공감을 할만한 설명밖에 안된다는 것을 스스로도 느끼는 풀이였네요. 조금 첨언을 하자면 큰 맥락은 피보나치 수열 문제와 동일합니다. 처음에 0,1을 준 상태에서 그 다음 값을 구할 때 x = 0+1, x' = x+1, ... 이런식으로 나가는 피보나치 수열 문제 또한 우리가 바로 전의 두 숫자를 더한다 라는 '식이 제대로 세워졌다고 믿고 그로 인해 나온 값들이 최적의 해' 라는 것에 동의하고 사용하는 것이 dp의 기본 개념이기 때문에 오늘의 풀이도 형태는 달라보일지언정 기본 개념은 피보나치 수열 문제를 풀 때와 동일하다는 점을 아신다면 이해가 되시리라 생각합니다. 다른 dp문제들도 똑같습니다.

 

조금 이해가 되셨나요? 혹시 잘 이해가 안되는 부분이 있다면 댓글로 물어봐주시면 감사하겠습니다.