[백준]#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

5
2
1
2
3
4

예제 출력 1

2
0
2
1
3

풀이

이 문제는 학생들이 쓴 수와 그 갯수를 구한 뒤에 학생들을 돌면서 그 학생이 쓴 수의 약수들의 갯수를 모두 더해서 답을 구했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int[] cnt = new int[1000001];   //수 세기위한 배열
        int[] ans = new int[N];

        for(int i=0; i<N; i++) {
            int x = arr[i] = Integer.parseInt(br.readLine()); //학생들이 쓴 수 저장
            cnt[x]++;   //학생들이 쓴 수 갯수 세기
        }

        for(int i=0; i<N; i++) {
            int temp = arr[i];

            for (int k=1; k*k <= temp; k++) {   //각 학생이 쓴 수의 약수 구하기
                if (temp % k == 0) {
                    ans[i] += cnt[k];
                    if (k*k < temp) {       //약수 쌍의 갯수를 더해줌
                        ans[i] += cnt[temp/k];
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++)
            sb.append(ans[i]-1).append("\n");   //자기 자신도 계산하기 때문에 -1씩

        System.out.print(sb);
    }
}