[BOJ] 계단 오르기_2579

해당 문제는 DP를 이용해서 풀었다.

 

dp[4] 이상부터는 dp[i] = max(dp[i - 2] + data[i], dp[i - 3] + data[i] + data[i - 1])코드로 dp값을 구할 수 있다.

그렇다면 왜 저 코드가 최대값을 의미하는가?

 

나는 dp를 풀 때, 문제를 보고 직접 써보며 규칙을 찾아내려고 하는 편이다.

 

그래서 찾은 규칙: 4번째부터는 해당 값이 최대가 되려면, 4보다 두칸 적은 계단까지의 최대값(dp[2])와 data[4] 

or 4보다 3칸 적은 계단까지의 최대값(dp[1])과 data3+data4를 더한 후

이 두개 중 최대값이 dp[4]값이 된다.

 

이 문제를 풀 때 dp[i-1]+data[i]와 같은 식으로 풀려고 했으나 그럼 dp[i-1]이 두칸 연속으로 얻은 값인지 or 그렇지 않은 값인지를 알아야 했다.

그래서 무슨 2차원 배열 어쩌구,,, 막 이상한 생각을 했는데 이러한 흐름으로 생각하기 보단,

 

계단이 1개일 때 최대값은? 2개일 떄 최대값은? 이런식으로 혼자 되뇌이다가 규칙을 발견한 것 같다.

그러다보니 4개쨰부터는 저러한 식이 성립됨을 알게 되었다.