Educational Codeforces Round 57 C. Polygon for the Angle

B번) 문제 링크 : https://codeforces.com/contest/1096/problem/C

입력으로 특정 각도가 주어진다. 이 때, 정다각형 내부에서 위와 같이 3개의 점을 연결해서 주어진 각도를 만들 수 있는 정n각형들 중 최소인 n을 찾는 문제이다.

우선, 수학적으로 알아야할 개념이 있다.

정n각형의 내각의 총 합 : 180 * (n-2)

위의 공식을 따라 (180 * (n-2)) / n 을 통해 정n각형의 한 각의 크기를 알 수 있다.

다음으로 알아야할 내용은 정n각형의 특징이다. 정사각형을 생각해보자. 정사각형에서 한 점에 대해 위 그림과 같이 추가적으로 이어줄 수 있는 점은 양 옆을 제외한 나머지 1개의 점( n-2 )이다. 이어줄 경우 정사각형의 한 각의 크기인 90도를 정확히 1/2하여 45도씩으로 나뉘게 된다. 마찬가지로 정오각형의 경우 108도를 1/3하여 36도씩으로 나뉘게 된다. 이 개념을 이용할 것이다.

이제 점을 이어서 나올 수 있는 최소각의 크기를 구할 수 있다.

최소각의 크기 : ((180 * (n-2)) / n) / (n-2) = 180 / n

즉, 정다각형에서 한 점에 대해 양옆을 제외한 다른 모든 변을 이었을 때 만들어지는 최소각의 크기는 180/n이다.

그럼 이제, 주어진 각도( 편의상 r이라 한다. )를 만들 수 있는지 보자.

r이 180/n으로 나누어 떨어진다면 해당 다각형 안에서 선을 그어서 만들 수 있는 각도가 되는 것이다. n=3부터 시작해서 n을 늘려가면서 나누어 떨어지는 경우를 찾는다면 최소가 되는 n을 찾을 수 있게 되는 것이다 !

하지만, 여기서 주의할 점이 있다. 각도로 144가 주어진다면, 위의 정오각형에서 만들 수 있는 최소각인 36도로 나누어 떨어진다. 하지만 144는 정오각형의 한 점의 내각보다 큰 값이다. 따라서 나누어 떨어진 몫이 n - 2 보다 작거나 같은지를 예외로 확인해주어야 한다.

+ 이 문제에서도 B번과 같은 자료형의 문제가 있었다. 180 / n을 했을 때 소수점이 생길 수 있으므로 float의 형태로 만들어서 받아줘야 한다. 하지만 마찬가지로 float one_ang = 180  / cur_n 과 같이 해준다면 틀린 결과를 받게 된다. 우변도 float으로 선언을 해주거나 형변환을 해서 수행해줘야 한다. 이거 해결하다가 9번 틀렸다..T^T

---

- 소스코드 -

#include<iostream>
using namespace std;
int main(void) {
	int T;
	cin >> T;
	for (int test_case = 0; test_case < T; test_case++) {
		int ang = 0;
		cin >> ang;
		int cur_n = 3;
		int result_n = 0;
		while (true) {
			float one_ang = (float)180  / (float)cur_n;
			
			float temp = (float)ang / (float)one_ang;
			if ((int)temp == temp) {
				if (ang / one_ang <= cur_n - 2) {
					result_n = cur_n;
					break;
				}
			}
			cur_n++;
		}
		printf("%d\n", result_n);
	}
}