N개의 꼭짓점을 가진 다각형에서 두 명의 아이가 각각 A와 B 꼭짓점에 서 있다고 가정해 봅시다. 이때 세 번째 사람이 서야 할 꼭짓점 번호를 구하는 것이 문제입니다. 조건은 세 번째 사람이 A와 B 양쪽 모두에 도달하기 위해 필요한 점프 횟수가 최소가 되어야 한다는 것입니다.
문제의 핵심 조건
이 문제에서 주목해야 할 두 가지 조건이 있습니다.
- 다각형의 꼭짓점은 시계 방향으로 번호가 매겨집니다.
- 정답이 여러 개일 경우에는 항상 가장 작은 번호의 꼭짓점을 선택합니다.
알고리즘 설명
vertexPosition(int sides, int vertexA, int vertexB) 함수는 다각형의 변의 개수와 꼭짓점 A, B의 위치를 매개변수로 받습니다.
for 루프는 1부터 시작하여 i가 변의 개수(N)보다 작거나 같을 때까지 반복합니다. i가 vertexA 또는 vertexB와 같지 않다면, i와 vertexA 사이의 절댓값 차이, 그리고 i와 vertexB 사이의 절댓값 차이를 각각 계산하여 x와 y에 저장합니다.
int vertexPosition(int N, int vertexA, int vertexB){
int tempSum = INT_MAX;
int sum = 0;
int position = 0;
for (int i = 1; i <= N; i++) {
if (i != vertexA && i != vertexB){
int x = abs(i - vertexA);
int y = abs(i - vertexB);다음으로 x와 y의 합을 sum 변수에 저장하고, 이 값이 tempSum보다 작은지 확인합니다. 만약 더 작다면 현재 sum 값을 tempSum에 할당하고, 현재 인덱스 값을 position 변수에 할당합니다.
if 문에서 새로 계산된 합이 tempSum에 저장된 이전 합보다 작은지 검사하는 이유는, A와 B로부터 가장 가까운 위치를 반환하기 위해서입니다. 루프가 모두 끝나면 position을 반환합니다.
sum = x + y;
if (sum < tempSum){
tempSum = sum;
position = i;
}
}
}
return position;
}전체 구현 예제
정규 N각형에서 세 번째 사람의 위치를 결정하는 전체 코드는 다음과 같습니다.
#include <iostream>
using namespace std;
int vertexPosition(int N, int vertexA, int vertexB){
int tempSum = INT_MAX;
int sum = 0;
int position = 0;
for (int i = 1; i <= N; i++) {
if (i != vertexA && i != vertexB){
int x = abs(i - vertexA);
int y = abs(i - vertexB);
sum = x + y;
if (sum < tempSum){
tempSum = sum;
position = i;
}
}
}
return position;
}
int main(){
int N = 6, vertexA = 2, vertexB = 4;
cout << "The vertex on which N should stand = " << vertexPosition(N, vertexA, vertexB);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.
The vertex on which N should stand = 6
이 예제에서 N=6(육각형), vertexA=2, vertexB=4인 경우, 세 번째 사람이 서야 할 최적의 꼭짓점은 6번입니다. 6번 꼭짓점에서 A(2번)와 B(4번)까지의 거리 합이 가장 작기 때문입니다.