mrseos   3년 전

안녕하세요 쉬운 계단수 문제를 풀고있는데, dp 테이블 작성과 점화식 구현에 어려움이 있어 질문드립니다.

제가 생각해본 경우는 아래와 같습니다.

N=1 case = [1, 2, 3, 4, 5, 6, 7, 8, 9], 9개

- 먼저 이게 계단수인지는 잘 모르겠으나 계단수라 가정을 해야 문제가 풀릴 것 같습니다.

N=2 [↓ 내려가는 계단수, ↑올라가는 계단수] 

case = [↓ 10, 21, 32, 43, 54, 65, 76, 87, 98

                  ↑ 12, 23, 34, 45, 56, 67, 78, 89,] , 

↓9+↑8 = 17개

N=3 case = [ ↓↑  101, 212, 323, 434, 545, 656, 767, 878, 989

                   ↓↓  210, 321, 432, 543, 654, 765, 876, 987

                   ↑↓ 121, 232, 343, 454, 565, 676, 787, 898                  

                   ↑↑ 123, 234, 345, 456, 567, 678, 789],

↓↑ 9 + ↑↓ 8 + ↓↓ 8 + ↑↑ 7 = 32개


N=2, 3을 고려하여 4일 때는

이전 단계에서 위 아래 방향이 계속 이어나가는 구조 [ 이 부분이 핵심인 것 같은데 dp 테이블을 어떻게 작성해야할 지 막막하네요..]

↓↑↑, ↓↑↓, ↓↓↑, ↓↓↓,  ↑↓↑, ↑↓↓,↑↑↑, ↑↑↓ 각 방향은 총 8개  

각 방향에 따른 dp 테이블을 작성해보고싶은데, 

문제가 쉽게 풀리질않아서 도움을 얻고자 질문하게 됐습니다. 

읽어주셔서 감사합니다!

kind4u   3년 전

질문주신 내용처럼 모든 계단수를 DP 테이블로 구현하기는 너무 비효율적이고, 수가 오를 수록 계산이 복잡해집니다.

문제에서 요구하는 것은 계단수의 개수이니, 계단수의 개수를 구하는 것에 중점을 두시고

이전 단계에서 다음 단계로 넘어갈 때, N=3의 경우 9,8,8,7등 불규칙적으로 보이는 수들이 이전 단계의 어느 부분에 영향을 받았는지 생각해보시면 좋을 것 같습니다.

mrseos   3년 전

감사합니다. 제공해주신 아이디어 덕분에 이번 문제는 해결했습니다.

계단수 관련 변형문제들도 한번에 풀어보고자 이런 질문을 드렸습니다.

좋은 하루 되세요^^

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