dp 04 Kingnight chess

책에서 이거 지금까지 해온거랑 똑같다고 해설 없이 풀어보라 그래서 하루 종일 고민했는데 모르겠다 ㅋㅋ 아 자괴감+1..

 

결국 해설을 보게 되었다 ㅠ

 

해설을 보고 왔는데 엥? 싶다. 이게 이렇게 된다고?

ways 배열을 만든다. 3차원 배열이다.

ways[row][column][nummoves]

그니까 좌표 0,1로 5번만에 갈 수 있는 방법의 수는 ways[0][1][5]에 기록되는거다.

그럼 이 3차원 배열을 어떻게 구성하냐?

 

dx = [1,1,1,0,-1,-1,-1,0,2,1,-1,-2,-2,-1,1,2]
dy = [1,0,-1,-1,-1,0,1,1,-1,-2,-2,-1,1,2,2,1]

ways = [[[0] * 55 for _ in range(100)] for _ in range(100)]

def howmany(size, start, end, nummoves):

    sx, sy = start
    ex, ey = end

    ways[sy][sx][0] = 1

    for i in range(1, nummoves+1):
        for x in range(size):
            for y in range(size):
                for j in range(16):
                    nx = x + dx[j]
                    ny = y + dy[j]
                    if nx<0 or ny<0 or nx>=size or ny>=size:
                        continue
                    
                    ways[ny][nx][i] += ways[y][x][i-1]

    return ways[ey][ex][nummoves]

 

의외로 너무 간결한 코드에 놀랬을지도 모른다.

나도 그랬으니까.

 

ny,nx 지점에 i번의 move로 갈 수 있는 방법의 수는

y,x지점에 i-1번의 move로 갈 수 있는 방법의 수의 합이라는 것 같다.

-> 왜 이런건지 직관을 못찾겠다

 

근데.. 잘 모르겠다 아직.. 이게 왜 되는거지?;;

일단 핵심은 단계별로 이동 가능한 곳에 +하는 거라는거.

 

고민좀 더 해봐야겠다..