d[100][10]에서 0~9가 모두 나타났는지 확인할 수 있는 상태만 추가해주면 되요.

그러면 d[100][10][1<<10]으로 해결할 수 있어요~

이해가 잘 안가네요 

d[100][10][1024]; 3차원 배열로 하라는 말씀이신가요? 

d[100][10][1024] 맞구요. 1024는 숫자가 방문 했는지 비트로 저장하면 됩니다.

정말 죄송한데

제가 대학에서 컴공을 전공한게 아니라서 

비트연산자를 응용하는법을 잘 모르겠습니다 

아이디어가 간단하면 조금만 더 설명해주시고 

조금 길다면 어느 부분을 공부해야하는지 말해주실수있나요 ??

9876543210에 방문한 애들을 표기하는 겁니다. 안했으면 0 방문했으면 1 다시방문해도 계속 1인거죠.
만약 3, 2, 1을 방문했다고 하면 0000001110으로 표현할 수 있습니다.
이는 2진수니까 이를 10진수로 표현하면 2+4+8=14가 되겠죠

그럼 이걸 왜 활용하냐면 |(or연산)의 경우 0|1이면 1이잖아요
그러니까 다음에 들어오는 숫자와 지금까지 방문한 정보를 비트로 저장해서 서로 or 연산해버리면
방문한 정보를 담고 있을 수 있게됩니다.

비트가 0부터 9까지 10개 필요하니까 2^10=1024로 나타낼 수 있는거죠.
그리고 14라는 숫자가 표현하는게 2, 4, 8을 방문했다는 유일한 정보입니다.
즉, 14라는 숫자는 다른 2,4,8말고 다른 숫자를 방문했다는 정보를 가질 수가 없죠..

d[n][x][a] = n이라는 길이의 계단수 맨 마지막 숫자가 x로 끝날때 a라는 비트 정보를 가지고 있는 방법의 수
d[n][x][bit|x] += d[n-1][x-1][bit]
이런식으로 bit가 가질 수 있는 모든 수 1, 3(1+2), 7(1+2+4), 15(1+2+4+8+...), ... 즉 10개의 수에 대해서만 체크해줍니다. (반복문 10번 돌리면 될 듯)

바로 위에서 마지막 말을 잘못했네요; 수 전체에 대해서 체크해줘야 하는군요.

2만 체크된 경우도 있고 3만 체크된 경우도 있을테니 ㅎ;

상세한 답변 감사합니다 ㅠㅠ 

차근차근읽어보고 완성해볼게요 

항상 배우고 갑니다. 

와 풀었습니다.

알아가면 알아갈수록 재밌네요 

감사합니다 ^^

함정은 저는 이 문제 아직 안풀었다는거 ㅋㅋ

도움이 되었다니 기쁘네요 ㅎ

나중에 질문 검색하실 분들을 위해 좀 더 적자면,

다 풀고나서 다른 분들 푼거 봤더니, 벽에 닿는 경우에만 bit를 조절해서 문제를 풀었더라구요.

즉, 9번에 닿으면 bit = 2, 0번에 닿으면 bit = 1, 아직 닿지 않은경우 bit = 0 -> 그럼 모두 닿으면 비트 3

이렇게 하면 d[100][10][4] 만으로도 해결이 가능합니다.

체크 좀 부탁합니다.

위에 설명을 보고 머리를 쥐어 짜도 아래와 같은 코드에서 벗어날 수가 없네요.

물론 틀렸다고 나오구요~~

뭘 더 고려해야 할까요?

위에 어떻게 코드를 작성하려고 하셨는지 잘 이해가 안갑니다. ㅎ;;
그래서 그냥 제가 푼 방법을 설명해 드릴게요.
제가 위에서 언급했던 방법은 각각 다른 방법입니다.

마지막에 언급했던 d[m][x][bit]는
m번째 인덱스부터 맨 마지막 인덱스까지의 계단수가 x로 시작하고(즉, m번째 인덱스가 x일 때) bit라는 정보를 가지고 있는 경우의 수 입니다.
즉, 처음 언급했던 d[m][x][bit]는 m이 감소하는 방향으로 체크가 되지만 마지막에 언급했던 방법은 m이 증가하는 방향으로 체크가 됩니다.

아무튼... 마지막에 언급했던 것을 점화식으로 표현해보면,
d[m][x][bit] = d[m+1][x-1][bit|mask1] + d[m+1][x+1][bit|mask2];
이렇게 됩니다.

x-1이 0일 때 mask1을 1로 해주시고,
x+1이 9일 때 mask2를 2로 해주시면
9번에 닿았을때 bit값이 2로 유지가 되고, 0에 닿았을때 2로 유지되던 bit값에 1이라는 정보가 추가되어 3이 될 수 있습니다. (반대방향으로도 마찬가지지요)
그럼 나중에 확인할 때에는 bit == 3인 애들만 모아서 x=1~9까지 더해주면 답이 됩니다.