[백준(BOJ)/C++] 3049번: 다각형의 대각선

백준 문제풀이

코딩밥상 2022. 8. 2. 15:53

3049번: 다각형의 대각선

세 대각선이 한 점에서 만나지 않는 볼록 N각형이 주어졌을 때, 대각선의 교차점의 개수를 세는 프로그램을 작성하시오. 아래 그림은 위의 조건을 만족하는 한 육각형의 교차점 그림이다. 모든

www.acmicpc.net

도형의 구성 요소의 개수를 세는 문제는 보통 서로간의 연관성에서 얻을 수 있다. 이는 보통 중학교 수학에서 배웠던 내용들이라 큰 어려움은 없을것이다.

다음 문제에서는 n각형 즉 꼭지점의 개수를 알려주었기 때문에 꼭지점과 문제에서 요구하는 답을 연관지어 생각하면 될것이다.

문제에서 요구하는 답은 꼭지점을 이어 만든 대각선들이 만나 생기는 교차점의 개수이다.

이를 연관지어 생각하면,

교차점이 생기려면 대각선이 두 개 필요하고

대각선은 꼭지점이 두 개 필요하다

따라서 교차점이 하나 생기려면 꼭지점이 4개 필요하다.

따라서 답은 n각형의 도형에서 4개의 꼭지점을 선택하면 된다.

여기서 꼭지점의 순서는 필요없기 때문에 nC4가 답이된다.