펜타토프 수(Pentatope Number)는 파스칼의 삼각형에서 다섯 번째 열(대각선)에 해당하는 수를 말합니다. '다섯 번째 수'라는 것은 파스칼 삼각형에 최소한 다섯 개의 숫자가 필요하다는 의미이며, 따라서 이 수열의 첫 번째 항은 파스칼 삼각형 네 번째 행인 1 4 6 4 1부터 시작됩니다. 이번 튜토리얼에서는 n번째 펜타토프 수를 구하는 프로그램을 만들어 보겠습니다.
입력 : 1 출력 : 1 입력 : 4 출력 : 35
다음 그림을 통해 각 값이 어디에 위치하는지 확인할 수 있습니다.
이 문제는 일종의 수열 문제입니다. 따라서 해결 과정에서는 수열이 가지는 규칙성을 먼저 찾아낸 뒤, 이를 활용하는 방식으로 접근합니다.
문제 해결 접근 방법
이 프로그램에서는 수열의 모든 항이 따르는 일반 공식을 도출합니다. 그런 다음 원하는 값을 공식에 대입하여 출력 결과를 얻습니다.
예제 코드
위 접근 방식을 구현한 C++ 코드
#include<bits/stdc++.h>
using namespace std;
int answer(int n){ // n번째 펜타토프 수를 구하는 함수
return (n * (n+1) * (n+2) * (n+3))/ 24; // 유도된 공식
}
int main(){
int n = 6; // 구하고자 하는 펜타토프 수
cout << answer(n) << "\n";
n = 4;
cout << answer(n) << "\n";
return 0;
}
실행 결과
126 35
위 코드의 전체 시간 복잡도는 O(1), 즉 상수 시간 복잡도입니다. 실행 시간이 입력 크기에 영향을 받지 않기 때문에 어떤 입력이 주어지더라도 동일한 속도로 답을 계산할 수 있으며, 이것이 달성 가능한 최적의 시간 복잡도입니다.
코드 이해하기
위 접근 방식에서는 수열의 패턴을 분석하고, 그 패턴으로부터 일반 공식을 유도했습니다. 최종적으로 얻어진 공식은 (n × (n + 1) × (n + 2) × (n + 3)) / 24이며, 여기서 n은 구하고자 하는 항의 순서를 의미합니다. 참고로 이 공식은 조합(combination) 관점에서 보면 C(n+3, 4), 즉 n+3개 중 4개를 선택하는 경우의 수와 같습니다.
마무리
이번 튜토리얼에서는 공식을 직접 유도하여 N번째 펜타토프 수를 구하는 문제를 해결했습니다. 이 문제에 대한 C++ 프로그램과 전체 해결 과정도 함께 살펴보았습니다. 물론 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 쉽게 작성할 수 있습니다. 이 글이 여러분의 학습에 도움이 되었기를 바랍니다.