PS/BOJ Python
1241번 - 머리 톡톡
zpqmdh
2022. 2. 15. 03:27
https://www.acmicpc.net/problem/1241
1241번: 머리 톡톡
엄지 생일 기념으로 학생들은 파티를 하고 있다. 엄지는 N(1≤N≤100,000)명의 학생에게 1부터 N번까지 차례대로 번호를 부여하였고 그들을 순서대로 빙 둘러앉아 원을 만들게 하였다. (즉 i번째 학
www.acmicpc.net
참고: https://kbw1101.tistory.com/32
[알고리즘] 효율적으로 약수를 찾는 알고리즘
코딩테스트 문제 중, 가끔 수학적인 기초를 묻는 문제에 약수, 배수 등의 문제가 출제된다. 이러한 유형의 문제를 접해본 경험이 없는 사람들은 최악의 시간복잡도를 갖는, 모든 경우를 찾는 순
kbw1101.tistory.com
#key: N의 약수를 구할 때는, 1부터 N의 제곱근까지의 수만 0으로 나누어떨어지는지 확인하면 된다
N = int(input())
number = [] #1~N번째 학생의 머리 위에 써있는 수
ans = [0] * N
maxValue = -1
#input
for i in range(N):
number.append(int(input()))
if number[i] > maxValue:
maxValue = number[i]
#number에 저장된 값 중에 가장 큰 수의 길이만큼 list 생성
#number에 저장된 수에 해당하는 cnt의 idx를 +1
cnt = [0] * (maxValue+1)
for i in number:
cnt[i] += 1
#입력받은 수들을 하나씩 돌면서 그 수의 약수를 하나씩 구한다
#ans에 그 약수에 해당하는 cnt 배열 값을 더해준다.
for i in range(N):
value = 1
while value*value <= number[i]:
if number[i] % value == 0:
if value*value != number[i]:
ans[i] += cnt[value] + cnt[number[i]//value]
else:
ans[i] += cnt[value]
value += 1
for res in ans:
print(res-1) #자기 자신의 개수 빼기