글 읽기 - c++시간초과 질문드립니다.

idcy 5년 전 0

자꾸 시간초과가 나서 다른 질문글을 읽고 long long으로 바꿔보았는데 그래도 시간초과가 뜨네요 ㅜㅜ

다른 테스트케이스를 넣었을 때 동작하는 걸 보면 틀린건 아닌거 같은데 어떻게 수정해야 할지 알려주시면 감사하겠습니다ㅜㅜ

시간복잡도에 대한 이해도가 낮아서 O(y-x)부분은 잘 이해되지 않더라구요

#include <iostream>
using namespace std;
int main() {
   long long x, y, testCase;
   cin >> testCase;
   for( long long k=0; k <testCase; k++){
      cin>> x >>y;
      long long dist = y-x;
      long long distCount = 1;
      long long maxCount=1;
      long long currentCount = 0;
 
      for(long long j=1;j<dist;j++){
         currentCount++;
         if(currentCount==maxCount){
            currentCount=0;
            if(distCount%2==0){
               maxCount++;
            }
            distCount++;
         }
      }
       
      cout<< distCount<<endl;
   }
}

k5nen 5년 전 0

아래 입력을 보면 3초를 조금 넘는 시간을 사용합니다.

https://ideone.com/l3ij5S

시간복잡도가 O(y-x)라는 뜻은 x, y가 입력으로 주어지면 대략 y-x에 비례하는 시간이 걸린다는 뜻입니다.

주먹구구식 법칙으로 보통 억 단위의 계산이 필요하면 수 초 이상의 계산시간이 필요합니다.

이 문제는 x, y에 상관없이 아주 짧고 빠른 시간 안에 풀 수 있습니다.

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

문제

문제

출처

ICPC

c++시간초과 질문드립니다.

idcy 5년 전 0

k5nen 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말