24267번 - 알고리즘 수업 - 알고리즘의 수행 시간 6
n=3 일때 1
n=4 일때 (2+1) + 1
n=5 일때 (3+2+1) + (2+1) + 1
이런식으로 되게끔 이중for문으로 짜봤습니다.
vs코드에서 확인했을 때 정답은 맞는 것 같은데 제출해보니 시간초과가 뜨네요ㅜㅜ
for문으로 안하고 n에관한 함수로 해보려고 했지만 잘 되지 않아서 질문합니다.
어떻게 해야될까요?
N^3 접근을 N^2으로 줄이셨지만 아직도 N<=5*10^5의 제한에 맞추려면 느립니다. 이 문제는 O(1) 혹은 O(N)의 시간복잡도의 풀이를 의도하고 있습니다.
for j <- i + 1 to n - 1 for k <- j + 1 to n
이 부분을 어떻게 O(1)에 계산 할 수 있는지 생각해보세요 (i와 n의 관계를 생각해보시면 해를 도출하실수 있을거예요)
우선 최고차항 3 구하신거는 잘 하셨습니다.
다만 이중 for 문을 돌리지 않고 구할 수 있는 방법이 있습니다. 힌트를 드리자면 반복문 조건 상, 중복되지 않게 n개 중 3개(i, j, k)를 구하는 방법을 공식으로 풀면 해결 가능합니다.
댓글을 작성하려면 로그인해야 합니다.
codingtaek2 2년 전
n=3 일때 1
n=4 일때 (2+1) + 1
n=5 일때 (3+2+1) + (2+1) + 1
이런식으로 되게끔 이중for문으로 짜봤습니다.
vs코드에서 확인했을 때 정답은 맞는 것 같은데 제출해보니 시간초과가 뜨네요ㅜㅜ
for문으로 안하고 n에관한 함수로 해보려고 했지만 잘 되지 않아서 질문합니다.
어떻게 해야될까요?