dp식은 맞은데, 결과값이 틀리게 나오는 경우, 초기값이 문제인 경우입니다.

dp[2][1]이 얼마일까요? 이걸, 소스코드로 돌려보면 2가 나옵니다.

왜 그러냐면. 이게 계산될 때

dp[1][0] + dp [1][2] 이렇게 계산되기 때문이죠. 이거 문제될 거 없잖아요?

네. 맞습니다. 근데 dp[1][0]이 1인 게 문제죠.

코드 의도상, 수 k로 끝나는 '조건을 만족하는 n자리 수'의 갯수는 k-1로 끝나는 n-1자리 자릿수

+ k+1로 끝나는 n-1자리 자릿수 정도가 되겠지요?

이 아이디어로 접근하는 건 맞아보입니다만..

문제는, 0으로 시작하는 수가 없다는 것이죠. 그리고..

오버플로가 나지 않는가? 이것을 다시 한 번 점검해 보세요. 굳이 나머지 연산을 많이 하기 싫으시다면 long long형으로 선언하고 1000000000으로 mod 연산을 하심 되겠다만..

dp 식을 세우실 때 중요한 건 2개입니다.

(1) 초기식 잘 세우기. 예를 들어, 콤비네이션을 구하는 경우

iC0 = 1 // iCi = 1 이래 되겠죠. (물론 i>=1)

(2) 관계식 잘 세우기

이 둘 중에, 하나라도 제대로 하지 않으면 답이 틀리겠죠.

다른 소스 참고하면서 작성했는데 코드는 이상이 없는 것 같습니다. (다른 사람이 정상적으로 정답처리됨)

그런데, 직관적으로 이해할때 dp의 경우 메모이제이션을 통한 단계적 경우의 수 접근인데, 제가 직관적으로 이해했을 부분에서 0이 1이고 2가 3인데 그 부분이 이해가 잘 안되서 그렇습니다..

(2)에서 문제가 있는 것이지요.

예를 들자면, 피보나치 수의 점화식은 f(x) = f(x-1) + f(x-2) 입니다.

이걸 관계식으로 잘 써 놓으셨습니다. ahn님 코드 보니 이 부분은 정말 잘 하신 거 같습니다.

그런데, 피보나치 함수 f(1)은 1인데, f(2)는 2인데, 뜬금없이 f(1) = f(2) = 30으로 해 놓으면

관계식이 맞아도 f(n)의 값은 원래 답하고 다르게 나오지 않을까요?

피보나치 3번째 수는 2이지, 60이 아니거든요.

ahn님 말씀대로 dp가 메모이제이션인지 뭔지. 아무튼

수식의 값을 저장해서, 중복되는 계산을 안 하도록 하는 목적이 있습니다. 그런데 기본적인 건.

초기 값이지요.

아래 코드가 무엇을 의미하는지 제가 정확히는 모르겠습니다만..

k자리 수에서, 조건을 만족하는 수를 초기화 시키기 위한 코드가 아닌가 싶어요.

여기서 보면 dp[1]. resize(11,1) 이렇게 들어가고 있지요.

이 이야기인 즉슨 dp[1][0] = ... = dp[1][x] = 1이라는 것이지요.

ahn님 의도는, 1자리 수에서, x로 끝나는, 쉬운 계단수를 만족하는 숫자의 갯수는 모두 1이다.

그렇기 때문에 이렇게 초기화를 하려고 했을 겁니다.

중요한 건, 0으로 시작하는 수는 없다는 것이죠.

그렇기 때문에 dp[1][0]은 1이 아닌 0이 되어야지요. 

일단, 2자리 수일 때, 계단수 한 번 출력해 보시겠어요?