오르막 수1 [C/C++] 11057: 오르막 수 최대한 점화식을 구하려고 생각하다보니 규칙을 발견하게 됐다! 다른 DP 문제와는 다르게 2차원 배열을 이용하여 DP를 저장해야지 풀려서 생각하는데 조금 시간이 걸린 것 같다. dp[n][n]에서 첫번째부터 생각을 해보면 dp[1]=1 1 1 1 1 1 1 1 1 1 => 10 dp[2]=10 9 8 7 6 5 4 3 2 1 => 55 dp[3]=55 45 36 28 21 15 10 6 3 1 => 220 . . . 이런 식으로 나아가는데 dp[i]와 dp[i-1]간의 관계를 살펴보면 dp[i][1]=dp[i][10]이고 dp[i][2]=dp[i][1]-dp[i-1][1] dp[i][3]=dp[i][2]-dp[i-1][2] . . 이런 식으로 나아간다. 따라서 이렇게 쭉 뻗어나가면 점화식을 얻을 수 있다... 2023. 8. 30. 이전 1 다음
