furyhunter   1년 전

재귀로 아래와 같이 작성해서 이것저것 돌려보는데 정답은 나오는 것 같습니다.

근데 제출해본 결과 시간 초과가 뜨더라구요..

시간을 줄이기 위해 동적계획법을 어떻게 적용하면 될지 감이 안와서 조언을 구합니다..

각 단계에서의 최댓값을 단일 배열에 저장해서 이용하는건가요?

감이 잘 안오네요..

waylight3   1년 전

가능한 경우의 수를 어떤 공간에 펼쳐놓는다고 생각해봅시다. 이 문제의 경우, i번째 계단에 대한 상태는 이전 계단에서 1칸 올라왔는지 2칸 올라왔는지만 알면 결정됩니다. 왜냐하면 그 이전의 정보는 몇 칸 올라왔는지를 제외하면 답을 구하는 데 전혀 필요가 없기 때문입니다. 따라서 (계단 수) X 2 만큼의 공간만큼 일종의 해 공간?이 존재합니다. 그렇다면, 이는 300 X 2의 2차원 dp테이블이 되니 이것만 채우면 답은 테이블 마지막에 들어있겠군요!

그럼 테이블을 어떻게 채우냐가 문제인데, 이 문제에서 계단은 올라갈수만 있다고 했으므로 다음과 같이 경우를 나눠볼 수 있습니다.

1. 방금 1계단 올라온 경우, 다시 1계단을 오르면 연속된 3계단을 밟게 됩니다. 따라서 이 경우 무조건 2계단을 뛰어야 합니다.

2. 방금 2계단 올라온 경우, 1계단 올라도 되고 2계단 올라도 됩니다.

따라서 다음과 같이 dp를 채워나갈 수 있습니다. 그렇다면 답은 dp[마지막 계단][1]과 dp[마지막 계단[2] 중 큰 값이겠군요!

(코드에서 step[i]는 i번째 계단의 점수를 의미합니다.)

furyhunter   1년 전

결국 중요한건 다음 인덱스의 계산을 위해서 필요한 이전단계들이 무엇인지 파악하는게 중요한거군요!

자세한 설명 감사합니다!

댓글을 작성하려면 로그인해야 합니다.