문제
https://www.acmicpc.net/problem/1241
문제해설
n명의 학생들이 각각 번호를 갖고 동그랗게 둘러앉아 있다.
한명씩 일어나서 한바퀴를 돌며
자신의 앞의 학생의 수가 자신의 수의 배수이면 그 학생의 머리를 친다.
한바퀴를 돌았을 때 몇명의 머리를 쳤는지 구하는 문제이다.
문제풀이
n이 최대 십만이고 학생이 가질 수 있는 수는 최대 백만이다.
문제를 그대로 구현한다면 시간초과가 발생한다.
n^2 연산을 수행하지 않고 문제를 풀어야 한다.
문제에서는 배수의 수를 세주지만 반대로 약수의 개수를 세주었다.
내가 때릴 수 있는 사람들을 체크해주는 것이 아니라
나를 때릴 수 있는 사람들을 봐준 것이다.
입력받은 수 중에 가장 큰 값 만큼의 공간을 가진 num이라는 배열을 만들어주고
그 배열에 입력받은 수 들을 ++해준다.
예를들어 3 5 4 9 3를 입력받는다고 하면
크기가 9인 배열을 만들어서
3에는 2, 4에 1, 5에 1, 9에 1이 들어가는 것이다.
그리고나서
입력받은 수들을 하나씩 돌면서
그 수의 약수를 하나씩 구한다.
그리고 결과 배열에 그 약수에 해당하는 num배열 값을 더해주었다.
그렇게 n번만 돌게되면 답을 구할 수 있다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n; cin >> n;
vector<int>arr(n);
vector<int>res(n);
vector<int>num;
int maxx = 0;
for (int i = 0; i < n; i++) {
cin >> arr[i];
maxx = max(maxx, arr[i]);
}
num.resize(maxx + 1);
for (int i = 0; i < n; i++)
num[arr[i]]++;
for (int i = 0; i < n; i++) {
for (int k = 1; k * k <= arr[i]; k++) { // 약수 구하는 알고리즘
if (arr[i] % k == 0) {
if (arr[i]/k != k)
res[i] += num[k] + num[arr[i]/k];
else
res[i] += num[k];
}
}
}
for (int i = 0; i < n; i++)
cout << res[i] - 1 << "\n"; // 자기 자신의 개수 빼줌
return 0;
}