[백준 / BOJ] 20157 화살을 쏘자

문제

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

20157번: 화살을 쏘자!

풍선들의 (X,Y)가 주어졌을때,

호준이가 화살을 쏠때, (화살은 포물선이 아닌 직선으로 날라감) 한번에 터트릴수 있는 풍선의 최대갯수를 구하는 문제다.

 

풀이

풍선의 갯수가 10만개이다. 

일반적인?? 완전탐색으로 모든경우를 볼경우 O(N^2)이 나와서 시간초과가 뜬다.

 

완전탐색으로 풀되, 저장을 다르게 해야하는데, 

 

나는 딕셔너리에

{기울기, 해당 기울기의 풍선의 갯수} 로 저장해 주는식으로 풀었다.

 

예를들어, (8,16)위치에 있는 풍선의 경우 ((1,2),1)로 저장을 해준다.

 

이때, (1,2)를 기울기인 2로 저장해놓지않는데, 그 이유가 이렇게 저장해놓을경우, C언어 표현 범위?를 벗어나는 소수에 대해서 (무한소수) 와 유한소수를 같은 기울기를 가지고 있다고 판단하기 때문이다.

 

예를들어,

 

무한소수 3.3333333333333333.......

와 

유한소수 3.3333333333333333

 

을 같은 기울기라고 판단하고 틀렸습니다가 뜬다. long double을 써도 틀림 

따라서 X좌표와 Y좌표의 공약수로 저장을 해줘야 한다.

 

그 이후, 모든 풍선에 대해서 같은 공약수를 갖고있는 풍선들을 찾아주면됨.

 

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/20157%20%ED%99%94%EC%82%B4%EC%9D%84%20%EC%8F%98%EC%9E%90/main.cpp

devxb/JJUNalgo