글 읽기 - 파이썬 별찍기 시간초과 질문입니다

dlawldjs02 3년 전 0

재귀 함수로 풀어보려 하는데 자꾸 시간 초과가 뜨네요. 어떻게 바꿔야 할까요?

n=int(input())
def star(n):
    if n==3:
        return [[1,1,1],[1,-1,1],[1,1,1]]
    x=[[0]*n for i in range(n)]
    for i in range(n):
        for j in range(n):
            if i//(n//3)==j//(n//3)==1:
                x[i][j]=-1
            else:
                x[i][j]=star(n//3)[i%(n//3)][j%(n//3)]
    return x
d={1:'*',-1:' '}
for i in range(n):
    for j in range(n):
        print(d[star(n)[i][j]],end='')
    print(end='\n')

slah007 3년 전 0

이렇게 하면 star(n)을 n^2번 호출하게 됩니다. star(n)을 한 번만 호출하고 값을 저장해둔 뒤 출력하세요.

dlawldjs02 3년 전 0

@slah007

이렇게 짜봤는데 시간초과가 계속 뜹니다. 저장을 이렇게 하는게 맞나요?

n=int(input())
def star(n):
    if n==3:
        return [['*','*','*'],['*',' ','*'],['*','*','*']]
    x=[[0]*n for i in range(n)]
    for i in range(n):
        for j in range(n):
            if i//(n//3)==j//(n//3)==1:
                x[i][j]=' '
            else:
                x[i][j]=star(n//3)[i%(n//3)][j%(n//3)]
    return x
a=star(n)
for i in range(n):
    for j in range(n):
        print(a[i][j],end='')
    print(end='\n')

dlawldjs02 3년 전 0

@slah007

아아 저장을 하라는 말을 잘못 이해했습니다. 이렇게 짜니까 통과되네요 감사합니다

n=int(input())
def star(n):
    if n==3:
        return [['*','*','*'],['*',' ','*'],['*','*','*']]
    x=[[0]*n for i in range(n)]
    a=star(n//3)
    for i in range(n):
        for j in range(n):
            if i//(n//3)==j//(n//3)==1:
                x[i][j]=' '
            else:
                x[i][j]=a[i%(n//3)][j%(n//3)]
    return x
a=star(n)
for i in range(n):
    for j in range(n):
        print(a[i][j],end='')
    print(end='\n')

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

문제

문제

출처

ICPC

파이썬 별찍기 시간초과 질문입니다

dlawldjs02 3년 전 0

slah007 3년 전 0

dlawldjs02 3년 전 0

dlawldjs02 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말