백준 계단오르기, DP 기본 지식 2일차

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

https://koolreview.tistory.com/180

설탕배달, DP 기본 지식 1일차

 DP 2일차, 사실 이 문제도 옛날에 풀었던 문제이지만, 그 당시에는 너무 어려워서 꽤나 괴로웠다. 그리고 정답 코드를 보고 너무 간단해서 좌절감을 느꼈었던 것 같다.

지금의 나는 이전보다 많이 달라졌으니, 시작해보자.

문제 위와 같은데 눈 여겨 볼만한 점은 3가지다.

1. 1단계씩 올라가기, 2단계씩 올라가기
2. 연속된 세 칸 밟기
3. 마지막 계단 밟기.

문제를 잘 읽으면, 1단계식 계속 올라가면 모든 점수를 얻을 수 있으니 제일 큰 값이다. 그런 경우를 막기 위해서 연달아서 3칸은 밟으면 안 되다는 조건이 달리고, 2단계식 올라갈 수 있는 선택지도 늘어났다고 생각해도 된다.

이전 글에서 이야기했듯이 이 문제도 완전탐색으로 해결이 가능하다.

먼저 처음에 선택할 수 있는 경우는 첫번째 칸, 두번째 칸이다.

파란색은 연속되어서 정답이 될 수 없다.

익숙하지 않은 개념이 하나 나온다. 연속되면 안 된다.우린 연속되지 않았다는 사실을 코드로 어떻게 표현할 수 있을까?

간단하다. 진짜 숫자가 연속되지 않으면 된다. -> ?

선택지를 고를 때 보자.

 무조건 첫번째를 선택한다고 가정했을 때 위처럼 2가지 경우가 생긴다. 왜 생기냐는 질문은 단순한 답이 있다. 최대한 많이 고르면 점수가 높다. 왜냐 각 요소들은 음수를 가지지 않지지 않기 때문에 무조건 많이 골라야 한다. 그렇기 때문에 위와 같이 고르는 경우가 제일 득점이 높다.

그렇다면 이를 코드를 어떻게 나타낼까? 아래와 같이 나타낼 수 있겠다.

다만 순방향으로 가면서 4개의 요소를 한번에 선택해서 계산해나가면 뭔가 안 맞는 느낌이 들 것이다.

이런 느낌은 이전 문제에서도 있었다. 재귀는 내려갔다가 다시 올라면서 값이 합쳐지면서 반환하게 된다.

그렇기 때문에 순방향으로 지나가면서 이전 값을 확인해야 한다.

그래서 아래와 같은 코드가 나오게 된다.

아직도 익숙하지 않다면 내일 또 봅시다. 아직도 1차원 상태라서 2차원으로 넘어가야 합니다!