글 읽기 - python은 시간초과, c++은 통과

cacosoda 3년 전 0

이 코드 그대로 C++에 맞게 써서 C++로 제출한건 통과했습니다.

python으로는 시간초과가 납니다.

접근 방식 자체의 문제인지 구현 상의 문제인지 궁금합니다...

N = int(input())
dp = [0,1]

for i in range(2, N+1):
  minimum = 10**7
  dp.append(0)
  for j in range(1, i+1):
    if j**2 > i:
      break
    elif j**2 == i:
      minimum = 1
      # if i = j**2, dp[i] = 1
      break
    else:
      result = 1 + dp[i - j**2]
      # i = j**2 + A
      # dp[i] = 1 + dp[A]
      if result < minimum:
        minimum = result
  dp[i] = minimum

print(dp[N])

wider93 3년 전 0

시간의 대부분을 차지하는 것이 if문이기 때문에 그걸 줄이는 방향으로 가면 될 것 같습니다. 8, 10번 줄을 합치기만 해도 꽤 나아질 것이고, i, j 포문의 순서를 바꾸는 것이 더 근본적인 해결책으로 보이네요.

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

문제

문제

출처

ICPC

python은 시간초과, c++은 통과

cacosoda 3년 전 0

wider93 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말