[백준] 27172 수 나누기 게임 (python 파이썬)

문제링크 : https://www.acmicpc.net/problem/27172

27172번: 수 나누기 게임

 

작성코드

 

풀이

 

플레이어의 수가 최대 100000 가 될 수 있기 때문에

문제에서 등장하는 결투(플레이어의 수로 다른 플레이어의 수를 나누어 나머지가 0이라면 이긴쪽에 +1, 진쪽에 -1 점 부여)를 진행하게 된다면 시간초과가 발생한다.

 

이를 해결하기 위해 에라토스테네스의 체의 풀이 방식을 응용한다.

에라토스테네스의 체는 소수를 찾는 방법으로

매번 계산을 하는 것이 아닌 배열을 만들고 숫자의 배수를 체크해주므로서 소수가 아닌 수를 빠르게 걸러주는 것이다.

 

이 문제의 풀이도 플레이어의 배수로 걸러주어 연산을 진행한다.

 

1) 입력받기, 빈 배열 만들기

빈 배열을 만들어 숫자 연산이 아닌 bool 처리로 빠르게 계산을 해준다.

 

 

2) 플레이어 등장여부 체크

 

3) 플레이어 수의 배수에서 만약 플레이어 등장 여부 확인 후 결투

플레이어 수의 배수를 돌면서 확인을 하는데 만약 2)에서 등장한 적이 있다면

j에 -1, i에 +1을 해주어 결투 승점 계산을 진행한다.

 

모든 플레이어 수에 대해서 계산 후 최종 score 값을 출력하면 된다.