원주 위에 K개의 등거리 점이 배치된 원이 하나 주어집니다. 여기에 두 점 A와 B가 추가로 주어지며, 우리의 목표는 이 점들을 활용해 내부에 둔각 ACB(90도보다 큰 각)가 존재하는 삼각형이 몇 개나 만들어질 수 있는지 세는 것입니다. 단, 두 점은 항상 A < B 조건을 만족한다고 가정합니다.
예를 들어 K=8, A=2, B=5인 경우, ∠ACB와 ∠AC'B가 둔각이 되도록 하는 점은 C와 C' 두 개입니다.
입력 및 출력 예시
입력 − k=10, A=2, B=4
출력 − 두 점 사이에서 만들 수 있는 둔각의 개수 − 1
설명 − 둔각을 만드는 점은 C=3 하나뿐입니다.
입력 − k=12, A=2, B=10
출력 − 두 점 사이에서 만들 수 있는 둔각의 개수 − 3
문제 해결 접근 방식
핵심 아이디어는 간단합니다. A와 B 사이의 더 짧은 호(shorter arc) 위에 있는 점들만 둔각을 형성할 수 있다는 것입니다.
따라서 두 호의 길이를 각각 계산한 뒤, 두 호의 길이가 서로 같다면 어떤 점을 선택해도 둔각이 만들어지지 않으므로 0을 반환합니다. 길이가 다르다면 더 짧은 호 위의 점 개수(간격 수)가 곧 정답이 됩니다.
알고리즘 단계
정수 k, point_a, point_b를 입력받습니다.
Obtuse_angle_circle(int point_a, int point_b, int k) 함수가 모든 변수를 받아 둔각의 개수를 계산해 반환합니다.
count 값을 0으로 초기화합니다.
첫 번째 호의 길이를 arc_1 = (point_b - point_a) - 1로 계산합니다. (b > a)
두 번째 호의 길이를 arc_2 = (k - point_b) + (point_a - 1)로 계산합니다.
두 호의 길이가 같다면 가능한 점이 없으므로 0을 반환합니다.
길이가 다르다면 count를 두 값 중 최솟값(min)으로 설정합니다. 모든 후보 점이 더 짧은 호 위에 있기 때문입니다.
count를 결과로 반환합니다.
C++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
int Obtuse_angle_circle(int point_a, int point_b, int k){
int count = 0;
int arc_1 = (point_b - point_a) - 1;
int arc_2 = (k - point_b) + (point_a - 1);
if (arc_1 == arc_2){
return 0;
}
count = min(arc_1, arc_2);
return count;
}
int main(){
int k = 10;
int point_a = 1;
int point_b = 4;
cout<<"두 점 사이에서 만들 수 있는 둔각의 개수: "<<Obtuse_angle_circle(point_a, point_b, k);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
두 점 사이에서 만들 수 있는 둔각의 개수: 2
이 알고리즘은 두 호의 길이만 비교하면 되므로 시간 복잡도는 O(1)로, 원 위의 점 개수가 아무리 많아도 즉시 답을 구할 수 있습니다.