백준 15488번 Python (메모리초과ㅠ)

ㅇ 내가 생각한 알고리즘

- 현재 좌표 모음(xy_list)에서 하나씩 꺼내서 말을 이동

- 말의 이동이 성공하면 임시 공간(temp_list)에 넣어줌

- 이 과정을 xy_list의 요소 수 만큼 반복

- 반복하면 temp_list를 xy_list로 넘겨줌

- 이걸 K번 반복

- 이동 성공 횟수는 최종적으로 남은 리스트 요소 갯수임

- 총 이동 횟수는 8**K제곱

 

ㅇ 나의 코드

import sys

input = sys.stdin.readline

N,x,y,K = map(int,input().strip().split())

steps = [(-2, -1), (-1, -2), (1, -2), (2, -1) ,

          (2, 1), (1, 2), (-1, 2), (-2, 1)]

xy_list = [[x,y]]

temp_list = []

for _ in range(K):

    for xy in xy_list:

      for step in steps:

        row = xy[0] + step[0]

        col = xy[1] + step[1]

        if row >= 1 and row <=N and col >= 1 and col <= N:

          temp_list.append([row,col])

    xy_list = temp_list

    temp_list = []

if K == 0:

  print(1)

else: print(len(xy_list)/8**K)

결과는 메모리초과....

이걸 어떻게 해결할수있을까...

해결을 한다면 다시 올려야지...

 

 

<해결함>

https://ie-mangchi.tistory.com/10

백준 15488 Python(해결)