글 읽기 - DP 접근으로는 python3 통과가 안되네요.

harry0558 1년 전 0

input n이라면 n+1개의 element를 할당하고 중첩 for문 때문에 일일이 검사해야 해서 시간이 꽤 소요되는데,

Brute-Force 방식으로는 python3에서 안전하게 시간 지체 없이 풀이가 통과되었지만,

아래와 같이 dp-table만들고 dp로 접근하는 방식으로는 시간 단축 풀이를 아무리 생각해봐도 python3로는 풀리지 않네요.

dp로 python3 맞힐 수 있는 아이디어가 있을까요?

알고 계시는 분 알려주심 정말 감사하겠습니다.

n=int(input())
dp=[0]*(n+1)
end = int((n-1)**(1/2))

num_squares = int(n**(1/2))

for i in range(1,num_squares+1):
    dp[i**2]=1

for i in range(1,n):
    for j in range(1,end+1):
        if ((i+j**2)<=n):
            if dp[i+j**2] != 0:
                dp[i+j**2] = min(dp[i+j**2],dp[i]+1)
            else: dp[i+j**2] = dp[i]+1

print(dp[-1])

djm03178 1년 전 1

12번째 줄의 조건이 만족되는 횟수에 비해 11번째 줄의 루프가 불필요하게 많이 돌고 있습니다. 한 번이라도 조건이 어긋나면 그 이후에는 바로 루프를 탈출해도 됩니다.

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

문제

문제

출처

ICPC

DP 접근으로는 python3 통과가 안되네요.

harry0558 1년 전 0

djm03178 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말