더블릿_선분상의 점

아.. 정말 고민하고 틀리기도 엄청 틀렸는데 이제는 

2번 정도 틀리는 문제는 과감히 포기하는 연습을 해야겠다. 어차피 여러번의 시도가 안되니까 말이다. 

-1억 ~ 1억 사이의 좌표 범위에서 

주어진 두 점의 선분에서 좌표가 정수로 떨어지는 점들의 개수를 찾는 문제였다. 

처음에는 굉장히 당황했고, 문제가 재귀라는데, 재귀를 사용하는 것에는 도무지 아이디어가 떠오르지 않았다. 

그래서 일단 시간초과를 감수하고라도 그냥 풀어야겠다고 생각했다. 

다 못 맞더라도 몇 개의 테스트케이스는 가져가는 로직을 짜야겠다는 생각을 한 것이다. 

내 소스의 치명적인 단점이 있는데, 선분이 주어지게 되는 경우의 수를 다 헤아리는데는 처음에 생각치 못한 예외가 굉장히 많았고 나는 그냥 그 것을 틀리면서 터득했다는 것이다. 좋지 않은 방법이라고 생각은 하지만 그래도 풀긴 풀어야 했다. 

예를 들어 두 점이 

(-1, -2) , (3, 4)

주어진다. 

1) 좌측 점을 0, 0으로 평행 이동시키면서 우측 점도 갱신한다.

-1, -2 => x 우측으로 1칸 위쪽으로 2칸 이동 시키면 0, 0이 되면 우측 끝 점은 (4, 6) 점이 된다.

2) 이렇게 나의 입맛에 맞추어 놓은 직선 y = ax 라는 방정식에서 a(기울기)를 구한다. 4,6을 대입하면 된다. 

a = 2/3이 된다. 

3) 이렇게 나의 입맛에 맞추어 놓은 직선을 x = 0 부터 ~ 우측 끝 점 4까지 순회하면서 정수를 찾는다.

모든 점들은 double형으로 선언했기 때문에

(a * i) == (int)(a * i) 가 참이 되면 이 것은 정수라는 것이다. 

4) 이렇게 개수를 구해줘서 출력해주면 된다.

다시 정리하자면

나의 방법은 좌측에 있는 점을 0, 0으로 평행이동 시키면서 0부터 우측점의 x 좌표 까지 순회하면서 

정수를 찾는 방법이었다. 

평행이동 시켰을 때는 

직선의 방정식은 y = ax 가 만들어진다. 0, 0을 한 점으로 가지고 있기 때문에, 

+b는 생략가능하다. 

이렇게 a라는 기울기를 구하고 x를 0 부터 우측 끝점까지 돌면서 x가 정수일 때 y도 정수인 점의 개수를 찾는 것이다.

다소 복잡하게 푼 점이 있지만 아이디어가 떠오르질 않아서 이렇게 푸는 수밖에 없었다.