7090d9d3283d60973678db1284a499c3.png

요새 열심히 문제풀고 있는 학생입니다. 이문제에서 도대체 어느 부분에서 시간초과가 뜨는 것이며 문제풀 때 시간초과가 뜨면 어딜 유의해서 봐야 하는지 알려주시면 감사하겠습니다 ㅠ

kesakiyo   2년 전

컴퓨터에서 기본적인 연산을 10억회 할 때 1초정도 걸린다고 보시면 됩니다.

그렇다면 최악의 인풋일때 qkrtjdrb9573 님의 코드에서는 최대 몇번의 연산이 일어나게 될까요?

이부분을 생각하신다면 시간제한이 1초인 이 문제에서 나이브하게 구현한 코드로는 억셉을 받을 수 없다는것을 알 수 있습니다.

그리고 int 로 입출력을 하시는데 인풋이 최대 10^15 인것을 주의해서 보셔야 합니다.

int 의 최대 표현 값이 -2^31 ~ 2^31-1 이니까요.

헐 감사합니다 ㅠ 그러면 어떤 특정한 알고리즘을 사용해야 한다는 뜻인거 같은데 어떤 알고리즘을 사용해야 하는 건가요 ?

pichulia   2년 전

0부터 99까지의 각 자리 수의 합은 어떻게 구할 수 있을까요? 

for문을 100번 돌면서 구해도 되겠지만  이렇게 생각할 수도 있습니다.

0부터 99까지 숫자를 만드는데 0이 20번, 1이 20번, 2가 20번...9가 20번 등장하는걸 알 수 있으니까 각 자리수의 합은 (0+1+2+3+..+9)*20 = 900 이다.

마찬가지 방법으로 0부터 99999까지 각 자리수의 합은

(0+1+2+...+9)*50000=2250000 (왜50000을 곱하는지는...비밀!!(....;;)) 으로 구할 수 있습니당

여기서 0부터 99가 아니라 100부터 199까지 각 자리수의 합은 

뒤의 두 자리수들의 합 900 + 세번째 자리수의 합 1*100 = 1000이 됩니다. 마찬가지로 200 부터 299까지의 합은 2 * 100이 더해진 1100이고요.... 1300부터 1399까지의 합은 (1+3)*100이 더해진 1300이겠네요ㅋㅋ

이제 이 성질을 이용해서, 0부터 n까지 각 자리수를 더한 합을 "~~00 부터 ~~99까지 더한 합"들의 합으로 변형시키게 되면 모든경우를 돌지 않아도 각 자리수의 합을 구할 수 있거됩니담ㅋ

예를들어 0부터 32136까지의 합은

(0~9999) + (10000~19999) + (20000~29999)+(30000~30999)+(31000+31999)+(32000~32099)+(32100~32109)+(32110~32119)+(32120~32129) + (32130~32136)

으로 분해가 가능하고, 각 괄호안의 영역에 해당하는 수들의 합은, 위에서 설명한 방법대로 계산해낼 수 있습니다...

딱히 이 글을 읽는다고 코드짜는게 쉬워지진않는다 판단해서 천기누설 해봅니당ㅋ

baekjoon   2년 전

스샷말고 소스 창에 복붙해주세요.

네 알겠습니다!!

흐아 너무 복잡하게 생각해서 그런가 아침부터 생각했는데 도저히 코드로 못쓰겠따 ...

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