교훈
문제를 곧이곧대로 풀 필요가 없다.
문제에 제시된 개념의 원리를 반영하여 풀기만 하면 된다.
약수라고 약수를 구하는 방법을 쓸 필요는 없다.
배수 개념을 활용하면 된다.
원래 짰던 코드
n = int(input())
s = 0
i = 1
while i <= n:
if i == 1:
s += 1
else:
k = 1
t = i ** (1 / 2)
while k <= t:
if i % k == 0:
r = i//k
if r != k:
s += k
s += r
else:
s += k
k += 1
i += 1
print(s)나는 약수라는 문제에 써진 개념에 충실했다.
-
첫 번째 시도 : 모든 숫자의 모든 약수를 다 테스트하기
처음에는 반복을 1~N까지 돌리고 그 안에서 또 1~i까지 돌렸다. 그런데 아무래도 시간이 너무 오래 걸리는 방법같았다. -
두 번째 시도 : 반복 횟수를 줄였다.
생각해보니 약수는 겹치는 개념이다. 매 숫자의 약수를 다 구할 때마다 해당 숫자보다 작은 모든 숫자로 나누어볼 필요가 없었다. 예를 들어, 6이 2로 나눠지니까, 6을 2로 나눈 몫인 3도 당연히 6의 약수!
그래서 어떤 숫자에 루트를 씌운 값까지만 반복문을 돌렸다. 그것이 바로 위의 코드 -
세 번째 시도 : 1에서 떠오른 아이디어
맨 처음에 더해지는 1은, 사실 예외처리를 한 것이었다.
그런데 생각해보면.. 저 1이 계속해서 반복되는 것 아닌가?
어떤 숫자도 다 1을 약수로 가지고 있다. 그래서 저 1은 불가피하게 n 번 반복되는 것이다! 그래서 고쳐볼까... 하다가 약수를 구해야 한다는 틀을 버리지 못해서 고치지 않았다.
그런데 계속해서 시간초과가 났다.
문제 그대로만 읽으면, 당연히 n^2의 시간복잡도를 피할 수가 없는 문제였다.....
이 문제는 약수 개념으로는 풀 수가 없고, 배수 개념을 활용해야하는 문제였음!!!
세번째 시도에서 떠오른 아이디어를 모든 숫자에 적용하면 되는 것이었다!!!
제출한 답
n = int(input())
i = 1
s = 0
while i <= n:
s += (n//i)*i
i += 1
print(s)짠..... 약수라는 개념을 붙들고 고전했던 시간이 다 무색해질 정도로 간단한 코드가 나왔다.
원리
원리는 이렇다.
n보다 작거나 같은 모든 수를 i라고 하고, 모든 i의 약수의 합을 더해야한다고 했을 때,
맨 아래에 각 약수들이 출현한 총계를 내보면 약수 안에서 개수가 몇 개씩 나오는지 보인다.
예를 들어,
n = 8이라서 i = 1 ~ 8까지일 때의 모든 약수를 더하는 거라면, 1은 8개, 2는 4개, 3은 2개가 나온다. 8을 각 숫자로 나눈 몫이 각 숫자가 출현하는 개수인 것이다!
제출 결과는 당연히 성공!!
사실 for문을 쓰면 더욱 짧은 코드가 나올텐데, while문이 더 빠를 것같다는 편견이 있었다.
근데 이거 진짜 while 이 for문 보다 빠른가???
번외) while v.s. for 시간비교
찾아보니 그렇지는 않다고 한다.
for문이 더 코드가 자동으로 처리해야 하는 연산이 많으니, while문을 활용하는 것이 더 빠를 것이라고 생각했다. 하지만 두둥,, 이 경우에는 for 문이 while문보다 더 빠르다고 한다! while문은 +1 을 더해주는 연산도 반복해야하기 때문이라고... 반복문 실행 중간에 종료 조건을 걸어야할 때가 아니라면 for문을 쓰는 것이 낫다고 한다. 나중에 조금 더 자세히 알아보도록 하겠다.
그래서 최종 코드는 for문으로 작성하여 한 번 더 제출했다.
n = int(input())
s = 0
for i in range(1, n+1):
s += (n//i)*i
print(s)결과는 당연히 성공~
그런데 백준이 테스트한 시간 결과는 while문이 더 빠르게 나왔더라구요..? 그래서 똑같은 for문 코드 한 번 더 넣어서 제출해봤더니, 이번엔 for문이 더 빠르게 나옴. ! 테스트 케이스 차이인가봅니다!
이 문제를 풀면서 떠오른 모든 의문점을 해결하고 후련하게 다음 문제 풀러 갑니다!
기초 문제인데 이렇게 시간을 쏟을 일인가 싶다는 생각이 든다면,,, 그럴 수도 있죠,, 근데 저는 궁금한 걸 다 해결하고 가야돼서,,, 그리고 그러면서 얻는 것도 많으니까~!!
저는 너무 후련하네요 히히 기분이 좋아~~
더 더 열심히 많은 걸 공부해야지!
이걸 읽고 계신 당신도! 늘 화이팅하세요!!!
