-
C++ 모두의 약수소프트웨어전공/알고리즘 문제풀이 2021. 9. 21. 20:23
문제 출처
https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/
일단 문제를 풀기 전에 종이에 나름 구현을 해보았다.
이중 for문을 이용하여 개수를 ++하는 방식으로 풀면 쉽겠다고 했는데
이상하리 엉뚱한 값이 나와서 해설을 보니..
각 숫자의 약수의 개수이기 때문에 개수를 i 마다 초기화 시켜줘야 한다..
"문제를 토씨 하나 빠짐없이 잘 읽어야 한다"
위 코드는 시간제한 1초를 만족시키지 못한다
반복문이 두번 도는 동안 j에서 불필요한 연산이 다시 i 만큼 돌게 된다. 따라서 시간복잡도가 O(n^2)에 거의 가깝다.
당장 아주 큰수를 넣어봐도 1초만에 답이 나오지 않는다 ( 약 2초정도 걸림 )
시간복잡도를 줄여야 하는데 중첩 반복문이 아닌 다른것을 생각해내야 한다..
(힌트 : 약수는 배수와 관련이 있다)
'소프트웨어전공 > 알고리즘 문제풀이' 카테고리의 다른 글
백준 1924번 _ 2007년 x월 y일은 무슨 요일? [C++] (0) 2021.09.23 백준 2741번 _ C++ ( 시간초과 해결하기 ) (0) 2021.09.22 C++ 모두의 약수 ( 제한시간 1초 ) (0) 2021.09.21 백준 11721번 _ C++ 열 개씩 끊어 출력하기 (0) 2021.09.21 백준 11720번 _ C++ 입출력 (0) 2021.09.21