[백준] 9937. 직선으로 만드는 삼각형

https://www.acmicpc.net/problem/9937

문제요약

• ${ax + by + c}$ 로 표현되는 직선이 30만개
• (다행히)세 직선이 한 점에서 만나는 일정은 없음
• 만들 수 있는 삼각형의 개수 구하기

접근법

• 기울기로 접근해야하는 것은 알겠음 : 서로다른 기울기 3개 조합
• 기울기가 같은 것은 카운팅 해야하는 것도 알겠음 : map 이용
• 조합을 시켜서 경우의 수를 구하는 방법
• 기울기 a, b, c를 각각 고르려고하니... 너무 많음
• 기울기를 나열해서 ${a_1, a_2, a_3,... }$ 라고 하면
• ${a_k}$ 입장에서는 ${..... a_{k-1}}$ 까지의 것 들에서 둘 간의 곱하기들의 합을 미리 알고 있다면 이용할 수 있음.
• 그리고 곱하기들의 합은 갱신도 가능함
• ${cnt(k)}$ : ${a_k}$의 기울기를 갖는 직선의 개수
• ${g(k)}$ : ${a_k}$까지 두 기울기간의 경우의 수의 곱의 합
• ${f(k)}$ : ${a_k}$ 까지 삼각형 조합의 수 = ${g(k - 1) * cnt(k)}$
• ${g(k) = g(k - 1) + sum(1...k-1) * cnt(k)}$
• ${ans = sum(f(1)...f(k)), k = 서로다른기울기의개수}$

다른 접근법

• 조합을 이용해서 뭔가 하는거 같은데 잘 모르겠다
• 알겠음. 어짜피 카운트 값을 아니까 그만큼 중복을 감안해서 계산을 했을테니 그만큼 보정해주면 됨. 예를들어 카운트가 10이면 전체 계산에서 10만큼 중복을 해서 계산한거를 보정한다는 개념