글 읽 기 - 동적 계획법 의 적용 에 대해 질문 이 있 습니다 . . 
 동적 계획법 의 적용 에 대해 질문 이 있 습니다 . . 
 furyhunter 1 년 전 0 
 재귀 로 아래 와 같이 작성 해서 이것저것 돌려 보 는데 정답 은 나오 는 것 같 습니다 . 
 근데 제출 해 본 결과 시간 초과 가 뜨 더라구요 . . 
 시간 을 줄이 기 위해 동적 계 획법 을 어떻게 적용 하 면 될지 감 이 안 와서 조언 을 구합니다 . . 
 각 단계 에서 의 최댓값 을 단일 배열 에 저장 해서 이용 하 는 건가요 ? 
 감 이 잘 안 오 네요 . . 
 waylight 3 1 년 전 12 
 가능 한 경우 의 수 를 어떤 공간 에 펼쳐 놓 는다고 생각 해 봅시다 . 이 문제 의 경우 , 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 번 째 계단 의 점수 를 의미 합니다 . ) 
 결국 중요 한 건 다음 인덱스 의 계산 을 위해서 필요 한 이전 단계 들 이 무엇 인지 파악 하 는 게 중요 한 거 군요 !