★★★☆☆
엄청 어려운건아니었는데, 2차원배열을 사용해서 하니까, 배열의 안에 어떤 값을 넣어줄지를 고민해줘야했다
스스로 난이도를 올려버림..(효율성은 낮아지고...)
직관적으로 이해하기에는 좋은 코드이지만 다른 풀이도 참고했다
나의 풀이
dp를 2차원 배열로 설정하고, 행은 n, 열은 2로 값을 잡았다
0번째 열은 앞에 2칸을 밟고 온 경우, 즉 연속 계단이 없는 경우이다.
이 경우, 앞에 2칸을 밟게 된 계단에서의 최댓값을 그냥 가져오면 된다.
따라서, dp[i][0]=max(dp[i-2][0],dp[i-2][1])+arr[i]
1번째 열은 앞에 1칸을 밟고 와서, 연속 계단인 상황이다.
이전에 1칸을 밟고 왔을 것이고, 그때 연속 계단은 없었을 것이기 때문에, dp[i-1][0] 의 값을 가져온다.
따라서, dp[i][1]=dp[i-1][0]+arr[i]
결과값은 2칸을 밟고 온 경우와 1칸을 밟고 온 경우의 max 값을 구해서 계산한다.
다른풀이
n번째 계단을 밟는 최댓값은 i-2번째에서 바로 지금 칸으로 오거나, i-3번째에서 2칸을 밟고, i-1번째에서 1칸을 밟은 경우이다.
따라서, dp[i]= max(dp[i-2]+arr[i],dp[i-3]+arr[i-1]+arr[i])
결론
확실히, 다른 코드가 훨씬 메모리를 적게 사용하고, 결과적으로 for문 안에서의 케이스도 줄어들기 때문에 훨씬 더 효율적이다. 굳이 2차원 배열을 사용할 필요가 없었던 문제였다.
https://github.com/jeongopo/DaliyCodeCpp/commit/b70461fea364cdede9a5cd66ec52398a64843e59
