백준 15488 Python(해결)

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

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

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 = [[0 for j in range(N)] for i in range(N)]

xy_list[x-1][y-1] +=1

temp_list = [[0 for j in range(N)] for i in range(N)]

for _ in range(K):

    for i in range(len(xy_list)):

      for j in range(len(xy_list)):

        if xy_list[i][j] != 0:

          for k in range(xy_list[i][j]):

            for step in steps:

              row = i+1 + step[0]

              col = j+1 + step[1]

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

                temp_list[row-1][col-1] += 1

    xy_list = temp_list

    temp_list = [[0 for j in range(N)] for i in range(N)]

if K == 0:

  print(1)

else:

  c = 0

  for i in range(N):

    c += sum(xy_list[i])

  print(c/8**K)

리스트의 크기가 커져 2차원 리스트를 초기화 하여 해보았지만 그래도 결과는 같았다.

 

ㅇ 메모리초과 원인(구글링 해봄)

- 2차원 리스트는 잘못사용하면 메모리문제가 발생할수가 있다고한다

 

ㅇ 해결방법

- 1차원 리스트를 2차원 리스트처럼 사용하였다.

- 몫과 나머지를 이용해서....

 

ㅇ 코드

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 = [0] * (N * N)

xy_list[(x - 1) * N + (y - 1)] = 1

temp_list = [0] * (N * N)

for _ in range(K):

    for i in range(N * N):

        if xy_list[i] != 0:

            for step in steps:

                row = (i // N) + step[0]

                col = (i % N) + step[1]

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

                    temp_list[row * N + col] += xy_list[i]

    xy_list = temp_list

    temp_list = [0] * (N * N)

if K == 0:

    print(1)

else:

    c = sum(xy_list)

    print(c / 8**K)