n²개의 정삼각형으로 이루어진 정삼각형 격자에서 정삼각형의 개수는 어떻게 셀까? 이 포스팅에서는 이에 대한 일반화를 해보려고 한다.
먼저 이러한 문제는 점화식으로 접근하는 것이 쉬울 것 같다. 먼저 사용할 점화식을 정의해주자.
a(n,k) = |한 변의 길이가 n인 정삼각형 격자에서 한 변의 길이가 k인 정삼각형의 개수|
자명하게 a(n,1) = n², a(n,n) = 1이다. 이제 a(n,k)에 대해서 생각해보자.
a(n,k) 을 계산할 때 위 그림에서도 볼 수 있듯이 a(n-1,k)에 새로 추가되는 정삼각형들을 더해주면 된다. 그럼 새로 추가되는 정삼각형의 개수를 구해보자.
1) 큰 정삼각형과 변이 평행한 정삼각형
이 경우는 구하는 정삼각형은 보라색 정삼각형이므로, n-k+1개가 된다.
2) 큰 정삼각형과 변이 평행하지 않은 정삼각형
1> n≤2k-2
이 경우에는 역삼각형이 추가되지 않는다.
2> n>2k-2
이 경우에는 n-k-1개씩 역삼각형이 추가된다.(n=2k-1인 경우는 0개 추가됨)
∴a(n,k) = a(n-1,k) + n - k + 1 (n≤2k-2)
= a(n-1,k) + (n - k + 1) + (n - k - 1) (n>2k-2)
= n² (k=1)
= 1 (n=k)
이제 이 점화식을 계산해보자.
1) n≤2k-2
a(n,k) = a(n-1,k) + n - k + 1
= a(n-2,k) + (n - k + 1) + (n-1 - k + 1)
= .....
= a(k,k) + ∑(i - k + 1) (k+1 ≤ i ≤n)
= 1 + (n-k)(n+k+1)/2 - (k-1)(n-k)
= (k² + n² - 3k + 3n - 2nk + 2)/2
= ((n - k + 3/2)² - 1/4)/2
2) n>2k-2
a(n,k) = a(n-1,k) + 2n - 2k
= a(n-2,k) + (2n - 2k) + (2n-2 - 2k)
= .....
= a(2k-2,k) + ∑(2i -2k) (2k-1 ≤ i ≤ n)
= ((k-1/2)² - 1/4)/2 + n² + n - 2kn + 2k -2
= (k² + 2n² + 3k + 2n - 4kn - 4)/2
점화식 계산이 조금 힘들지만 이렇게 구할 수 있다. ㅎㅎ
+추가로 dp를 이용해서 n에 대해서 모두 구하는 코드도 짜보았다.
#include <iostream>
using namespace std;
int a[100][100];
int main()
{
int A,k,n;
cin>>A;
for(k=1;k<=A;k++)
{
if(k==1)
{
a[A][k] = A*A;
}
else{
for(n=k;n<=A;n++)
{
if(n == k)
{
a[n][k] = 1;
}
else
{
if(n<=2*k-2)
{
a[n][k] = a[n-1][k] + n-k+1;
}
else
{
a[n][k] = a[n-1][k] + 2*n - 2*k;
}
}
}
}
cout<<k<<" : "<<a[A][k]<<"\n";
}
}
'수학' 카테고리의 다른 글
nCr을 소수 p로 나눈 나머지 구하기 루카스 정리(Lucas's Theorem) (0) | 2024.03.03 |
---|---|
Airplane Boarding Problem 비행기 타기 문제 (1) | 2024.02.04 |
격자 도형의 넓이 구하는 픽의 정리(Pick's theorem) (0) | 2024.01.03 |
몬즈의 정리(Monge's Theorem) (0) | 2023.12.23 |
페르마 포인트, 스타이너 포인트와 그의 확장 (1) | 2023.12.17 |