글 읽기 - 시간초과

duddndtod 4년 전 0

대부분의 테스트 케이스에 대해서 정답을 맞추긴 하는데 속도가 2초가 넘는 것 같아 질문 드려요

혹시 어느부분을 고치면 속도가 상승할지 알려주실수 있을까요?

개인적인 생각으로는 min([answer_list[content - (int(content**0.5)-i)**2 - 1][1] for i in range(int(content**0.5))]) 이 부분에서의 계산을

줄여야 할 것 같은데 아이디어좀 주시면 감사하겠습니다

def square_sum(answer_list,content):
    if square_check(content) == True:
        answer_list[content-1][1] = 1
    else:
        answer_list[content-1][1] = 1 + min([answer_list[content - (int(content**0.5)-i)**2 - 1][1] for i in range(int(content**0.5))])

def square_check(N):
    if N == int(N**0.5)**2:
        return True
    else:
        False

N = int(input())
answer_list = [[k+1,0] for k in range(100000)]

for i in range(N):
    square_sum(answer_list,answer_list[i][0])

print(answer_list[N-1][1])

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

문제

문제

출처

ICPC

시간초과

duddndtod 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말