글 읽기 - 뭐가 문제일까요...

lsaac 1년 전 0

code blocks에서 짜고 돌렸을때는 예시처럼 출력이 되는데 여기서 제출하니까 시간초과라고 나옵니다.

제가 추측하기론 int값을 long long값으로 바꿔줘야 하는거 같은데 맞나요?

#include <stdio.h>

int main()
{
    int a, b, v;
    scanf("%d %d %d", &a, &b, &v);
    int count = 0;

    if (a == v){
        printf("%d", 1);
        return 0;
    }

    while (1)
    {
        count++;
        v = v - (a-b);
        if (v - a == 0){
            printf("%d", count+1);
            break;
        }
        else if (v <= 0){
            printf("%d", count);
            break;
        }
    }
    return 0;
}

wak8835 1년 전 0

이 문제는 다음의 최악 조건에 따른 시간 복잡도로 유추해보시면 감이 잡히실 것 같습니다.

2 1 1000000000

1초를 보통 1억(=10만^2)번 연산 수행이라고 계산하여 제한시간인 0.15초라 하였을 때에 1500만(=15,000,000) 안에 결과가 나와야하는데,

현재 만드신 반복문 수행으로 위 조건을 수행하였을 때에 10억번, 약 10초를 수행하게 되는 꼴이니 잘못된 접근 방법이라 봐야겠습니다.

+ 수치 오타 수정

lsaac 1년 전 1

그럼 시간초과가 나는 원인은 반복문이고 반복문을 어떻게든 바꿔야된다는 말씀이신가요?

wak8835 1년 전 1

정확합니다. :)

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