[백준] 31864 눈송이 탕후루 만들기

31864번: 눈송이 탕후루 만들기

 

 

 

 

 

 

 

풀이 아이디어

0,0에서 끝점까지의 선을 기준으로 하기 때문에

모든 탕후루는 반드시 기울기가 같은 끝점에만 꽂힐 수 있다.

 

따라서 끝점을 기준으로 순회하며

0,0과 끝점사이의 기울기가 같은 탕후루가 몇개인지를 확인하면 되는 문제이다.

 

브루트포스로 풀 경우 최악의 경우 모든 눈송이와 끝점이 같은 선상에 있는 경우가 존재하며

따라서 O(n*m)이 나올 수 있다. 

 

그렇기 때문에 최적화 방법으로 이분탐색을 추가했다.

 

기울기를 키값 하는 배열을 만든 다음

x좌표를 벨류 값으로 넣고 정렬 시켰다.

 

그 다음 입력 받는 좌표로 기울기를 구한다음 그 기울기에 해당하는 배열에서 x값을 토대로 이분탐색해서

갯수를 구했다.

x나 y좌표가 0일때도 있는데 이건 예외처리해서 다른 배열에 담아서 따로 해결했다.

 

 

좌표가 0일때를 예외 처리하면 

기울기 값과 x또는 y 좌표만으로 중복 없이 각각의 탕후루를 담을 수 있다.

 

 

시행 착오

기하학이나 자료구조 문제가 취약해서 풀어본 문제였는데

익숙하지 않다보니 기울기를 단순히 long double로 처리했었고, 다행히 정답처리를 받았다.

 

다만

부동 소수점은 정확도면에서 많이 떨어지는데

 

다른 분들이 풀어본 걸 보니 최대공약수를 구한 다음 소수 값으로 변화한 다음

소수 좌표로 문자열을 만들어 키값으로서 사용한 걸 볼 수 있었다.

확실히 문자열 방법이 더 정확도가 높은 것 같다고 생각한다.

 

c++은 오름차순으로 되어야 lowwer bound가 제대로 작동하기 때문에

0,0을 기준으로 8방향으로 나눠서 조건분기로 풀었다.

 

 

최적화 해보기

일단 내가 풀었던 것 처럼 8방향까지 갈 필요 없이

 

x와 y 중  0이 포함 될 때와

그렇지 않을 때

총 두가지 나눈 다음 푸는게 나아보인다.

 

 

기울기를 키값으로 하는 배열을 만들어 정렬하고 이분탐색으로 푼다는 가정하에

정렬하는 비용 n log(n)

기울기를 기준으로 이분탐색 하는 비용 log (n)

끝점 순회 m으로

 

풀어본 풀이법의 시간 복잡도는

O(max(m*log(n) , n*log(n)))이다.

 

 

아직 기하학과 자료구조의 견문이 부족해서

 

굳이 최적화를 더 해보자면

시간 복잡도가 최악의 경우는 모든 과일과 모든 끝점이 같은 선상에 있을 때이다.

 

끝점에 대해서도 gcd를 구해서 중복된 끝점을 제외한다면

(맵을 사용해서 중복을 걸러낸다면 O(m)이면 해결될 것 같다.)

 

중복이 없을 경우의 최악의 경우만 남으므로

 

n = n1 + n2 + n3.... 일 때

시간복잡도는 log(n1) + log(n2) + log(n3)... 임으로

 

O(max(log(n1) + log(n2) + log(n3) ....  , n*log(n)))로 풀 수 있다.