kalmiaa   5달 전

안녕하세요.


다른분들 글을 보니 dp[a][b] 를 시작지점(1)에서 a를 거쳐 N을 간후 돌아올때 b를 거쳐가는 경우의 수라고 하는것 같더군요.

그렇다면 

dp[a][b] = dp[a로부터갈수있는 돌(b제외)][돌아오는 길에 b를 밟기 전에 밟을 수 있는 돌(a제외)]

로 정의하면 되는것 같습니다.


숫자로 이야기하면,


5 다음에 밟을 수 있는 돌이 6 7 8 이고

오는길에 7을 밟기전에 밟을수 있는 돌을 8 9 11 이라고 했을때

dp[5][7] = sum(dp[5][8], dp[5][9], dp[5][11],dp[6][7],dp[6][8], dp[6][9], dp[6][11], dp[8][7], dp[8][9], dp[8][11])

이라고 정의했습니다.


하지만 제 생각이 잘못되어서, 간단한 사례조차 답이 제대로 나오질 않고 있습니다.

기저사례를 dp[1][1]로 잡고 dp[a][b] (a<=N, b<=N) 까지 돌리고 있습니다만, 중복된 계산도 많고,

같은 돌을 2번(갈때, 올때) 밟은 경우의 수도 합산되고 있습니다.


어떻게 접근해야 할지 조언 부탁드립니다.

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