우선 처음 문제를 보자마자 dp로 접근해보고 싶어서 이차원 배열 dp를 선언했어요. (dp[i][j]: 위치 i에서 j의 시간이 흐르기까지 눈덩이 크기의 최댓값 -> i는 현재 눈덩이의 위치, j는 현재까지 흐른 시간)

예를 들어, dp[0][0]인 경우는 현재 위치가 0이고 시간=0이므로 눈덩이 크기의 초기값 1이 되고, 이제 dp를 적용하기 위해 bottom-up 방식으로 i=2부터 문제에서 주어진 조건대로 dp[i][j]= max(dp[i-1][j-1]+a[i], dp[i-2][j-1]+a[i])로 설정해봤습니다. max에서 첫째 식은 문제에서 눈덩이를 한 칸 움직였을 때의 경우이고, 둘째 식은 두 칸 움직였을 때의 경우에요.

또 i가 만약에 눈덩이가 한번에 움직일 수 있는 거리의 최댓값과 현재까지 흐른 시간의 곱(즉, 2*j)보다 크면 아예 존재할 수 없는 경우라고 생각하고 dp의 값을 0으로 해 주었어요. 또 현재까지 흐른 시간이 현재 위치값보다 큰 경우는 있을 수 없는 경우라고 생각하고 이 값 또한 0으로 해 주었어요.

이렇게 해서 최종적으로 대회 제한시간인 m초가 지난 순간의 눈덩이의 최대 크기인 dp[i][m] 중에서 i=0~i=2*m(m초동안 눈덩이가 움직일 수 있는 거리의 최댓값) 으로 반복문을 돌면서 최댓값을 구해주면 문제의 답이 나올 것이라 생각했는데 틀렸다고 나오네요. 여러번 생각해 봤는데 어느 부분에서 접근을 잘못했는지 잘 모르겠네요.. 또한 애시당초 dp로 접근하는 것이 적합한 문제인지도 궁금합니다.