시간초과 관련

Question

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 3474번 교수가 된 현우 문제에 궁금한 점이 있어 질문 드립니다. 숫자를 나열하다가, 강의에서 말씀해주신 방법을 생각해서, 코드 짜다가 시간 초과가 떴는데,, https://www.acmicpc.net/source/share/3c9d463fe36f42c99af74c905cf07162 https://www.acmicpc.net/source/share/e822ffb921674445b1098545cfa86544 for문의 변수 여부가 시간 초과를 만들 정도로 큰 영향을 미치는지 궁금합니다.   https://www.acmicpc.net/source/share/93e297d9280a42d09bde543ed7af790b 이 코드의 경우에는 50%에서 시간 초과가 뜨는데, 어느 부분이 안 좋은 부분인지 큰돌님의 생각을 듣고 싶습니다!

큰돌 · Answer

안녕하세요 kim님 ㅎㅎ 이 문제의 n의 범위가 얼마일까요? 1,000,000,000 무려... 이정도나 됩니다. (10억입니다. ) 그렇기 때문에 이를 그냥 for문으로 돌리면 당연히 시간초과가 나는 것이죠. 아래는 kim님의 코드 : for (int i = 5, j = 5; i <= n; i += j ) { int tmp = i; for문의 변수 여부가 시간 초과를 만들 정도로 큰 영향을 미치는지 궁금합니다. >> 네 for문을 반복해서 10억을 돌린다던가 등을 하게 되면 당연히 시간초과가 납니다. 시간복잡도는 1억이하, 1000만 이하 정도 수준으로 구축하시는게 좋습니다.   또 질문 있으시면 언제든지 질문 부탁드립니다. 감사합니다. 강사 큰돌 올림.