백준 2579 - 계단 오르기

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

의외로 까다로웠던 문제. 여러 풀이를 찾아보고 겨우 이해했다.

 

해결 포인트 : 현재 계단(i)에 오기 직전에 어느 칸에 있었는가?

1. i-1칸 -> i-1칸이 i-2칸을 경유했다면 i-2, i-1, i 연속된 3칸을 밟게 되므로,

i-1칸은 반드시 i-3칸에서 두 칸 이동해 와야한다. dp[i-3] + score[i-1]

2. i-2칸 -> i-1칸을 경유하지 않았기 때문에 i-2칸이 어떤 경로로 왔던지 연속한 3칸을 밟지 않는다.

dp[i-2]

 

dp[i] = max(dp[i-3] + score[i-1], dp[i-2]) + score[i]

dp[i-3]에 접근해야 하므로 i=3부터 출발하며, 따라서 i=2까지 dp[i]가 setup 되어 있어야 한다.

 

이번 문제는 사람마다 풀이 방식이 다양했기에, 지금은 풀이를 참고해 답을 제출했지만

다음에는 나만의 풀이를 찾아 답을 제출해 보면 좋을 듯 하다.

 

배운 내용 :

substructure 생성 ->

어디까지 값이 확정되어있어야 하는가? 답을 계산하기 위해 메모이제이션 배열의 어느 부분이 필요한가?

std namespace에서 max를 제공함 -> define 안 해도 됨