다이나믹1

• 

  백준 - 계단 오르기 문제 설명 계단오를때 점수를 받는다. 계단을 오를때 점수를 받을 수 있는 총 점수를 구하는 문제이다. 단 ,규칙이 존재한다. 연속된 3 계단을 밟아 점수를 얻을 수 없다. 마지막 계단은 반드시 밟아야 한다. TRY 계단의 최대 입력으로 들어올 수 있는 수는 300이다. 이것은 기본적으로 완전탐색을 한다면 시간 초과가 나올 수 있다. 다이나믹으로 풀어낼 수 있다. dp[i]=MAX(dp[i-2]+ dp[i-3] + stair[i-1])+ stair[i] 위점화식을 해석하면 현재 계단에서 뒤로 두번째 칸을 밟아왔던 값 ,뒤로 세칸 밟아왔던 값 + 뒤로 한칸 밟은 값 이다. dp[i-3] + stair[i-1]은 역속된 3칸을 밟지 않아야한다는 조건때문이다. dp[i-1]만 보면 dp[i-1]이 이미 연속된 .. Algorithm/백준 2023. 4. 11.