1241(머리 톡톡) - 해결

머리 톡톡

 

문제

엄지 생일 기념으로 학생들은 파티를 하고 있다. 엄지는 N(1≤N≤100,000)명의 학생에게 1부터 N번까지 차례대로 번호를 부여하였고 그들을 순서대로 빙 둘러앉아 원을 만들게 하였다. (즉 i번째 학생은 i-1과 i+1학생 사이에 앉아있다. 단, N번째 학생은 N-1번째 학생과 첫 번째 학생 사이에 앉아있다.)

N명의 학생은 둘러앉아 "머리톡톡" 게임을 하려한다. 게임 규칙은 다음과 같다. 각각의 학생은 자신의 머리 위에 1,000,000 이하의 자연수 중 하나를 쓴다. 그리고 1번부터 N번 학생까지 한 명씩 차례대로 일어나 원을 돌면서 자신이 쓴 숫자가 다른 사람이 쓴 숫자의 배수이면 그 학생의 머리를 "톡톡" 친다.

문제는 각각의 학생이 일어나 자신의 자리로 돌아올 때까지 총 몇 명의 학생의 머리를 치는지 구하는 것이다.

 

입력

첫째 줄에 학생의 수 N이 입력되고 다음 N개의 줄에는 1번부터 N번까지 각각의 학생이 자신의 머리에 쓴 숫자를 입력받는다.

 

출력

총 N개의 줄로 i번째 줄에는 i번째 학생이 한 바퀴를 돌면서 머리를 친 학생의 수를 출력한다.

---

브루트포스하게는 숫자의 크기가 크기때문에 그 방법보다는 수학적으로 생각하였다.

각 숫자를 인덱스 리스트에 저장하고, 카운트 리스트로 갯수를 저장하였다.

그리고 1~1000000까지 돌면서 각 숫자가 있으면 그 숫자의 배수에 해당 숫자의 갯수만큼 더 해주는 식으로 하였다.

그렇게 하면 각 숫자의 배수에 그 수의 약수 갯수를 저장할 수 있다.

그리고 마지막으로 해당 자기 자신을 빼야하기 때문에 - 1을 하였다.

import sys
input = sys.stdin.readline

N = int(input().strip())

# 숫자 카운트를 하기 위해서
num_list = [0] * 1000001
# 각 숫자 저장
idx_list = []

# 숫자 카운트와 숫자 저장
for _ in range(N):
    n = int(input().strip())
    idx_list.append(n)
    num_list[n] += 1

result = [0] * 1000001

# 1~1000000까지 순회
for i in range(1,1000001):
    # 해당 숫자가 있는지 확인
    if num_list[i] == 0:
        continue
    # 있다면 해당 숫자의 배수에 
    # 해당 숫자의 갯수만큼 더해준다.
    for j in range(i,1000001,i):
        result[j] += num_list[i]

# 각 숫자에서 자기 자신을 빼고 출력
for i in idx_list:
    print(result[i] - 1)