백준 2725번 보이는 점의 개수

< 백준 2725번 보이는 점의 개수 - 마포 코딩박 >

사용한 알고리즘: DP


 N이 주어졌을때 NxN 그래프 위의 점 중 원점에서 보이는 점의 개수를 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 6~7)
 'dp[i]: ixi 크기의 정사각 좌표들 중 원점에서 보이는 점의 총 개수' 로 설정합니다.
 dp[i] = dp[i-1] + (추가로 보이는 수) 입니다.

(2) (코드 14~33)
 dp[1]~dp[1000] 을 구하는 함수를 만듭니다.
 (i-1)x(i-1) -> ixi 로 확장될 때 새로 생기는 선분은 정사각형의 윗변과 오른쪽변입니다.
 (추가로 보이는 수) = 2*(새로생기는 윗변에 추가로 보이는 수) = 2*((i,1)~(i,i) 중 추가로 보이는 수) 입니다.
 점 (x,y)가 보이는지 여부는 기울기로 판별합니다.
 (x,y) 가 보이는 점일 때 기울기 y/x 를 bool 배열로 기억하고, 이후는 보이지 않는다 생각합니다.