1037번-약수
1과 자기 자신을 제외한 약수들이 주어질 때 그 수를 구하는 문제이다. 결론적으로, 약수 중 가장 작은 값과 큰 값을 구해 곱하면 된다. 나의 풀이는 아래와 같다.
n = int(input())
div=list(map(int, input().split()))
ans = 0
if n == 1:
ans = div[0]*div[0]
else:
ans = max(div)*min(div)
print(ans)처음에는 입력 시에 정렬된 상태임을 가정하고 풀었는데 그것이 아니었다. 그래서 시간을 좀 잡아먹었다.
이 문제에서 주목할 만한 것은 띄어쓰기로 되어있는 문자열을 받아서 그것을 하나하나 잘라 리스트로 다룰 때이다. 그것을 위한 코드는 다음과 같다.
div=list(map(int, input().split()))17427번-약수의 합2
이 문제는 시키는 대로 코드를 작성했다. 그래서 아래와 같은 코드를 작성했다.
n = int(input)
def function_f(n):
i = 1
ans = 0
while i <= n:
if n%i == 0:
ans += i
i += 1
return ans
ans = 0
for i in range(n):
ans += function_f(i+1)
print(ans)그러나 계속 런타임에러가 떴다. 제한 시간을 살피지 않은 것이다. 제한 시간은 0.5초 이다. 그러나 위의 코드대로 복잡도를 계산해보면 아무리 줄여봐야 O(루트 N)이다. 즉, N의 최대값인 1000000을 집어넣어보면 복잡도가 약 10초 정도이다. 따라서 약수를 직접구하는 방법으로는 제한 시간을 맞출 수 없다.
따라서 배수로 찾아가야한다. 어찌됐건 N이하의 숫자들의 모든 약수를 구하는 것이기 때문에 N을 N보다 작은 자연수로 나눈 개수 만큼의 약수가 들어있을 것이다. 다음 이미지로 이해할 수 있다.
이를 토대로 배수의 개수를 구하고 그 수를 곱한 것을 합하여 구하는 방법은 단순하게 연산만 하는 것이므로 O(N)의 복잡도를 가진다. 따라서 제한 시간을 만족한다. 아래의 코드로 구현했다.
n = int(input())
ans = 0
i = 1
while i <= n:
ans += (n//i*i)
i += 1
print(ans)17425번-약수의 합
위의 약수의 합 2 문제의 알고리즘을 사용하면 최대시간이 약 1000초이다. 그렇기 때문에 우리는 배수의 방법을 적용할 것이다. 한 가지 알고 있는 사실은 N까지의 수 중 약수인 수의 개수가 아닌 수보다 월등히 적다. 그러므로 우리는 N의 최댓값까지 약수의 합을 전부 구하고 입력된 수를 그 안에서 찾아서 출력할 것이다. 이 경우 복잡도는 O(NlogN)이다. 아래는 이를 구현한 코드이다.
MAX = 1000000
div = [1] * (MAX+1)
s = [0] * (MAX+1)
for i in range(2, MAX+1):
j = 1
while i*j <= MAX:
div[i*j] += i
j += 1
for i in range(1, MAX+1):
s[i] = s[i-1] + div[i]
n = int(input())
ans = []
for _ in range(n):
i = int(input())
ans.append(s[i])
print('\n'.join(map(str, ans))+'\n')div는 N 까지의 수의 각 수에 대한 f함수 값, 즉 약수의 합을 나타낸 것이다. g함수 값은 s 리스트에 담겨있다. 리스트의 길이를 MAX+1로 한 이유는 인덱스 0의 값을 신경쓰지 않게 하기 위함 인 것 같다.
여기서 알게 된 것이 2가지가 있다.
하나는 unscored _ 이다. 이는 위 처럼 인덱스가 필요없이 단순 반복을 위한 도움장치이다.
두번째는 리스트의 세로 출력 방법이다. 전에는 반복문으로 주르륵 출력했다면 이 코드에서는 직접 그 형태의 반복문을 \n을 이용하여 만들었다.
print('\n'.join(map(str, ans))+'\n')