[백준] 2579번 계단 오르기

벌써부터 귀찮다. 점화식부터 세워보자

<그림 1> 을 예시로 들고 3번째 계단까지 올라가며, 최대 점수를 구한다고 하면 ( N = 3 )

두가지 방법이 있다

1 번째 계단을 밟고 3 번째 계단을 밟기 ( 10 + 15 )

2 번째 계단을 밟고 3 번째 계단을 밟기 ( 20 + 15 )

둘 중 더 높은 점수를 구해야 하니 3번째 계단의 최대 점수는 35

4 번째 계단까지 올라가며, 최대 점수를 구한다고 하면 ( N = 4 )

1 번째 계단을 밟고, 2 번째 계단을 밟고, 4 번째 계단을 밟기 ( 10 + 20 + 25 )

1 번째 계단을 밟고, 3 번째 계단을 밟고, 4 번째 계단을 밟기 ( 10 + 15 + 25 )

2 번째 계단을 밟고, 4 번째 계단을 밟기  ( 20 + 25 )

4 번째 계단의 최대 점수는 55

결국 N번째 계단을 밟으려면, N-1 또는 N-2 번째 계단을 꼭 밟아야 하므로 

첫 번째 :  N - 1 계단까지 밟은 후, N 계단을 밟은 경우

두 번째 :  N - 2 계단까지 밟은 후, N 계단을 밟은 경우 

두 번의 경우를 구하면 될 것 같다.

<점화식으로 만들어낸 첫번째 재귀함수>

그런데, N - 1 계단까지 밟은 후를 생각해 보면, 만약 N이 3이라면 ?

n-1 함수를 먼저 만나니, N-1, N-1, N-1 을 해 N 이 0일때까지 들어갈 것이고, N = 1일때 값은 10 vs 10으로 맥스값은 10

이제 N = 2 일때, 값은 30 vs 20 맥스값은 30

N = 3 일때, 값은 45 vs  25 맥스값은 45... 뭔가 이상하다. 위에서 구했을땐 맥스값이 35가 나와야 한다.

곰곰히 생각해보니 clime(n-1,f) +f[n]은 n-1 번째, 그러니까 바로 앞 계단을 계속 밟고 구해온 것이다. 연속으로 3칸 이상은 밟으면 안되니까.

45일때가 바로 앞 계단을 밟았다고 하는거니까.. N-1 번째 계단을 밟고, N 계단을 밟으려면 N-3번째 계단을 밟고 오는 수밖엔 없다.

그럼 N-3 번째까지의 최대점수를 구한다음, N-1 번째의 계단 점수를 합치고, N 계단의 점수를 합치는건 어떨까?

그럼 N이 3일때 맥스값은 0 + 20 + 15 로 맥스값 35가 나온다.

<첫번째 재귀를 수정한 버전>

이제 대충 작성했으니, dp로 다시 수정한다.

맞다 dp로 수정한 소스에선 delete[] dp, delete[] f 를 깜빡했다.

제출한 소스에는 잘 적었다.

풀고 나니 허망하다. 이 문제 하나푼다고 7시간동안 머리 싸매고 있었다.

첫번째 점화식을 재귀함수로 만들었을때 아 드디어 다 풀었구나 했고 그때는 겨우 20분밖에 쓰지 않았다.

백준과 똑같은 예제로 넣었는데 값이 다르게 나와서 멘탈이 박살났고

퇴근 후 잠도 못자고 계속 생각해내다가 n-1 을 계속 타고간다는걸 보고 급하게 수정해봤더니 맞았다.

진짜 힘들었다 아 ㅋㅋㅋ