[백준 / BOJ] 1241 머리 톡톡

문제

출처 : www.acmicpc.net/problem/1241

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] 를 더해준다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1241%20%EB%A8%B8%EB%A6%AC%20%ED%86%A1%ED%86%A1/main.cpp

devxb/JJUNalgo