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

gigohe2 2년 전 0

n과 m에 20억이하로 들어오고,

int형 tmp에서 나누기 연산만 하니 범위초과는 나오지 않을 것이고,

2와 5가 곱해져있는 갯수를 세어 0의자릿수를 판별해봤는데요..

만약 20억이랑 1이 주어지면 연산이 너무 길어질 것 같습니다.

이게 시간초과의 이유일까요?

#include <stdio.h>

int main()
{
    int n,m;
    scanf("%d %d", &n, &m);
    
    
    int two=0;
    int five=0;
    int tmp;
    for(int i=n; i>m; i--)
    {
        tmp=i;
        while(tmp%2==0)
        {
           two++;
           tmp/=2;
        }
        while(tmp%5==0)
        {
            five++;
            tmp/=5;
        }
    }
    
    for(int j=1; j<=(n-m); j++)
    {
        tmp=j;
        while(tmp%2==0)
        {
            two--;
            tmp/=2;
        }
        while(tmp%5==0)
        {
            five--;
            tmp/=5;
        }
    }
    
    if(two>five)
    {
        printf("%d", five);
    }
    else
    {
        printf("%d", two);
    }
    return 0;
}

qkfskan82 2년 전 1

PS에서 주어진 시간 1초는 1억번의 연산으로 보시면 됩니다.

언어마다 조금씩 다르긴 하지만 이 문제에선 2초가 주어지니 2억번의 연산 안에 풀이를 끝내야하는데, 말씀 하신 것처럼 지금 보이는 코드에선 시간초과가 날 부분이 너무 많네요..

우리가 수학에서 조합을 구하듯 풀지 마시고 압축 가능한 방법을 고려하시는게 좋을것 같습니다.

(hint : 5!를 소인수 분해하면 5^1 이, 10!을 분해하면 5^2가 25!를 분해하면 5^(5 + 1) 이 나옵니다.)

풀이를 검색해서 이해하고 푸시는 것도 좋습니다!! 수학이 필요한 문제는 늘 어렵네요...

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

문제

문제

출처

ICPC

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

gigohe2 2년 전 0

qkfskan82 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말