문제
출처 : www.acmicpc.net/problem/1241
N명의 학생이 원형으로 앉아있다.
1번 학생부터 N번 학생까지 순서대로 일어나면서 자신이 쓴 숫자가 다른사람의 숫자의 배수라면 머리를 한대친다.
이때 각학생이 머리를 총 몇번치는지 구하는 문제이다.
풀이
완전탐색으로 풀게되면 100001 * 50000이라 시간초과가 난다.
arr배열을 만들어 해당 숫자가 나온 횟수를 저장해주고,
약수가 되는 값의 범위를 찾아 풀었다.
i번 학생이 머리에 든 숫자의 루트값 까지 돌려가며 풀었다.
현재 학생이 머리에 든 숫자가 100 이라면, 약수는
(1 2 4 5 10 20 25 50 100) 이 된다.
이때 10까지 반복해준다. (20 25 50 100 은 각각 1 2 4 5를 반복했을때 이미 봐줬기때문에)
이때, check 배열을 만들어 현재 학생이 머리에 든 숫자를 이미 탐색했었다면 바로 출력해준다. 아니라면,
i = 1부터 i <= 10(100의 루트값) 까지 탐색을하며
1. num % i = 0 이라면 미리 저장해둔 arr배열에 있던 값을 더해준다. (arr[i])
2. num / i != i 라면 (100 의 약수중 마지막인 10을 두번더해주는걸 없애줌) arr[num / i] 를 더해준다.
소스코드
'알고리즘 (2020 : 08 : 10 ~ ) > 수학' 카테고리의 다른 글
[백준 / BOJ] 1256 사전 (0) | 2021.04.04 |
---|---|
[백준 / BOJ] 17087 숨바꼭질 6 (0) | 2020.12.28 |
[백준 / BOJ] 1629 곱셈 (0) | 2020.08.25 |
[백준 / BOJ] 1105 팔 (0) | 2020.08.19 |
[백준 / BOJ] 14650 걷다보니 신천역 삼 (small) (0) | 2020.08.18 |