hcjy97   2년 전

문제 자체는 이미 풀었는데

탐색 범위를 정할 때 n이 최댓값일 경우 결과값을 아는 게 중요하잖아요.

고수분들의 댓글을 보니까 n이 10000일 경우에 3000000이 안 된다는 걸 알고 문제를 푸시는 것 같은데

생초보라서 그런가 이런 걸 어떻게 계산해야 하는지 감이 오지 않습니다.

대충 최댓값을 4000000으로 때려맞춰서 문제는 풀었는데 아무래도 찝찝하기도 하고

저 스킬을 알아야 앞으로도 문제를 원활하게 풀 수 있을 것 같아서 고견을 여쭤봅니다.

dongwanpianist   1년 전

문제에 맞춰 짧은 시간 안에 실행되는 알고리즘을 구현하기 전에,

소요 시간과 상관 없이 일단 구현해서 상한선을 알아내는 것이 중요하겠죠?... 예를 들어 666 앞으로 넉넉하게 다섯자리, 666 뒤로 넉넉하게 다섯자리, 즉 xxxxx666yyyyy 로 가능한 수 (666부터 9999966699999까지)를 모두 저장하는 벡터를 생성해보세요. (단, 뒤 y의 길이는 0자리부터 5자리까지 가능)

시간이 너무 오래 걸리면 10000번째가 논리적으로 어느 수 이상 크지 않다고 생각하면 y 자리수에 의해 x부분을 제한을 할 수 있고요..

이렇게 하면 느리면 1분이상 넘어가는 원시적인 알고리즘이지만, 느리고 완벽하게 계산하여 10000번째가 어떤 수인지 직접 알아보실 수 있습니다.

그 숫자를 상한선으로 해서 더욱 효율적인 코드로 바꿔서 제출하실 수 있겠죠~

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