C++로 원을 N번 잘랐을 때 조각 수 계산하기

정수 N은 하나의 2차원 원에 적용된 절단 횟수를 나타내며, 각 절단은 원의 중심을 지나면서 원을 둘로 나눕니다. 목표는 N번의 절단이 끝난 후 원이 몇 개의 조각으로 나뉘는지 구하는 것입니다.

모든 절단이 중심을 지나는 경우에는 아래와 같은 간단한 공식으로 조각 수를 구할 수 있습니다.

조각 수 = 2 × 절단 횟수

예시로 이해하기

예시 1

입력: N = 1
출력: 원의 조각 수 = 2

설명: 절단 한 번이 원을 정확히 두 부분으로 나눕니다.

예시 2

입력: N = 3
출력: 원의 조각 수 = 6

설명: 세 번의 절단이 모두 중심에서 만나므로 원은 여섯 개의 조각으로 나뉩니다.

접근 방식

1. 절단 횟수 N을 입력받습니다.
2. 공식 pieces = 2 * N을 사용해 조각 수를 계산합니다.
3. 계산된 결과를 출력합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N = 2;              // 절단 횟수
    int pieces = 2 * N;     // 조각 수 계산
    cout << endl << "원의 조각 수: " << pieces;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

원의 조각 수: 4

복잡도 및 참고 사항

이 알고리즘은 곱셈 한 번만으로 답을 구하므로 시간 복잡도와 공간 복잡도가 모두 O(1)입니다.

참고로, 절단선이 반드시 원의 중심을 지나야 한다는 조건이 없다면 결과는 달라집니다. 서로 다른 위치에서 교차하는 N개의 직선 절단으로 만들 수 있는 최대 조각 수는 N(N+1)/2 + 1개입니다. 본 문제는 모든 절단이 중심을 지나 매번 두 조각을 추가한다고 가정하기 때문에 2×N이라는 공식이 성립합니다.