문제 42, 땅 나누기, How many Pieces of Land?, PC/UVa ID : 110602/10213, 인기도 : B, 성공률 : 보통, 레벨 : 2

이 포스트를 만든 목적

  • 생각 절차, 푼 방법, 고민거리 등을 기록하기 위해서 만들었다.

이 포스트의 준비물

  • Mozila Firefox 6.0
  • eclipse 3.6.1 + vrapper
  • java

참조 문헌

  • 스티븐 스키에나, 미구엘 레비야 저. Programming Challenges: 알고리즘 트레이닝 북. 서환수 역.
    Springer. 한빛미디어 초판 2쇄 2004.12.05. (문제 42, 땅 나누기, How many Pieces of Land?, p.173)

참조 링크

간략한 이야기/프로그램의 입출력

타원 모양의 땅이 주어졌고, 그 땅 테두리에 n개의 점이 지정한 뒤, 각 n개의 점을 서로 이었을 때, 최대 몇조각으로 땅이 분리 되는가? n개의 점이 주어였을 때, 선분의 갯수는 n(n-1)/2 개 이다. 다음은 n=6 일때, 땅이 나뉜 모습이다.

입력

  • 첫번째 라인에는 테스트 캐스으의 갯수가 입력되며, 0 < s < 3511 작은 정수 s가 입력된다.
  • 다음줄 부터는 0 <= n < 2^31 미만의 수가 입력되며, n 은 점의 갯수이다.

출력

  • 한줄에 하나의 결과만 출력한다.

맛보기 사진

맛보기 코드



여담

  • 선이 서로 출돌될 때, 조각 하나가 생기므로, 충돌 선의 갯수를 조사한 공식으로 만들었다.
  • 충돌 공식을 만들기 위해 원을 30개쯤 그렸다.

  • 충돌 공식은 각 점에 인덱스 0 ~ n - 1 를 부여하고, 0 ~ n - 1 개의 점을 일일이 선을 그으면서, 충돌될 선을 샌 것이다.

  • 충돌 갯수를 for 문으로 조사하기 때문에, 2^31 - 1 개의 점이 있을 때, 무척 느린 성능을 나타낸다.(결국 속도 개선을 위한 알고리즘 변경이 필요함)

:wq!

  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 라이프코리아트위터 공유하기
  • shared
  • 카카오스토리 공유하기