Baekjoon(백준) 17441번 - 파리채 만들기

백준 사이트의 17441번.
문제 제목 : 파리채 만들기
백준 17441

사실 알고리즘적인 사고를 요구하는 문제는 아니고 그냥 수학 문제였다. 서울대학교 프로그래밍 대회에서 만든 문제 같은데… 글쎄 프로그래밍 대회에 내는 문제라기에는… 좀 그랬다. 익숙하지 않은 형태랄까.
그냥 문제 이리저리 둘러보다가 ‘그린 정리’ 카테고리에 이 문제 하나밖에 없어서 풀어보기로 한 문제이다. (왠지 하나 밖에 없는 건 꼭 건들고 싶은 심리…)

문제 해석

(단순) 다각형의 꼭짓점들을 반시계 방향 순서대로 나열한 입력이 주어진다. 다각형 내부에서 두 개의 점이 있을 때 두 점 사이의 거리를 $d$ 라 한다. 이 때 $d^2$의 기댓값을 구해야 한다. (어떤 점이 영역 내부에 존재할 확률은 (영역의 넓이) / (전체 넓이) 로 정의한다)

풀이 전략

수학적으로 뭔가 풀어야 한다는 것까지는 감을 잡았고 이리저리 식을 정리해보았으나 잘 되지 않았다. 그래서 초반부 아이디어만 다른 풀이를 참고해서 식 정리와 전개 등은 직접 했다. 그냥 수학적으로 해석해서 푸는 문제이기 때문에 별다른 알고리즘 같은 건 없고 식을 정리해서 도출하게 된 과정을 아래에 나타냈다. 대학 과정인 Calculus에서 배우는 Green’s theorem 을 사용하는 풀이이므로 모른다면 이를 다시 보고 풀이를 보는 것이 좋을 듯 하다.

구현

위의 식들 중 가장 마지막에 도출된 $E(d^2)$ 의 식을 그대로 프로그램에 넣어서 계산하면 된다. 다각형이므로 $(x_i, y_i)$에는 각 꼭짓점의 좌표를 대입하면 된다. 주의할 점은 프로그램 상에서 계산을 할 때 모든 숫자는 double 형으로 처리된다는 점에 유의하고 그런 값들을 처리할 때 중간에 값이 최대한 왜곡되지 않도록 여러가지를 고려해야 한다. (double 형으로 캐스팅 하거나 등등… 혹시나를 위해 최대한 왜곡되지 않도록 해놓는 것이 좋을 듯 하다)

자세한 solution은 github에 있다.

아 그리고 남은 이번 방학 동안은 인공지능에 관한 공부를 중점적으로 할 예정이다. 인공지능 관련 포스트를 올릴 수도 있고 아니면 아무 포스트도 안 올릴 수도 있고 다시 문제 풀이 포스트를 올릴 수도 있다… (바쁘다!)

baekjoon 17441 solution code