인프런 커뮤니티 질문&답변
작성한 질문수
1-O 질문 드립니다.
작성
·
492
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
코드 공유:
http://boj.kr/da52b00cdb43479badaf49dceb395e13
숫자가 커짐에 따라 pow 함수가 시간복잡도에 미치는 영향이 큰지 궁금합니다!
업로드 해주신 모범답안을 보면 1로만 이루어진 배수를 찾기 위해
S_n = S_n-1 * 10 +1
이러한 식으로 수를 만들면서, 오버플로가 발생하지 않도록 매번 모듈러 연산을 처리한걸로 이해했습니다.
반면에, 저는 문제를 푸는 과정에서 1로만 이루어진 배수를 만들기 위해 pow(10, x)를 통해 1부터 10, 100, ... 을 매번 더하는 식으로 했습니다.
위 링크의 28, 29번 줄과 같이 1로만 이루어진 수를 만드는 과정에서만 다소 차이가 있는데, pow 함수를 사용한 코드는 33프로에서 시간초과가 나와서 여쭤봅니다!
혹은 다른 부분에서 제가 미처 확인하지 못한 부분이 있다면 알려주시면 감사하겠습니다!
답변 1
0
안녕하세요 life님 ㅎㅎ
숫자가 커짐에 따라 pow 함수가 시간복잡도에 미치는 영향이 큰지 궁금합니다!
>> 크지 않습니다.
반면에, 저는 문제를 푸는 과정에서 1로만 이루어진 배수를 만들기 위해 pow(10, x)를 통해 1부터 10, 100, ... 을 매번 더하는 식으로 했습니다.
>>자 그러면 pow함수를 통해서 하시는 것은 알겠는데요. pow()로 나오는 값이 long long 범위보다 커지지 않을까요?
또 질문 있으시면 언제든지 질문 부탁드립니다.
감사합니다.
강사 큰돌 올림.
답변 감사합니다!
모듈러연산의 분배법칙 응용을 계속 생각하다 보니, pow함수를 통해 더해주는 값 자체가 long long 범위를 벗어나는 것을 생각 못했습니다.
진심으로 감사합니다 :)