개념을 알았으니 문제를 풀어볼 시간이다.
파스칼의 삼각형은 꽤 흉악하게 생겼지만, 알고 보면 여린 아이이다.
문제를 해결하기 위해서는, 우선적으로 삼각형을 이루는 항들 사이의 관계를 알아야 한다.
파스칼의 삼각형이란 이항계수를 삼각형의 모양으로 나타낸 것이다. 그렇다는 것은, 같은 행렬의 이웃한 두 항의 합이 두 항 사이에 있는 밑 행의 항이라는 것이다. 따라서, 파스칼의 삼각형을 회전변환 시켰을 때, 각 항을 P(행, 열)이라 했을 때
P(r, c) = P(r-1, c) + P(r, c-1)과 같이 표현된다.
코드를 짜보자.
#include <stdio.h>
long long f(int m, int n)
{
if(m<=0 || n<=0) return 0; // m,n이 0이하인 항은 존재하지 않음
else if(m==1 || n==1) return 1; // 첫번째 행, 열은 모두 1임
else return (f(m-1,n) + f(m,n-1))%100000000; // 점화식을 100000000으로 나눈 값
}
int main()
{
int r,c;
scanf("%d %d", &r, &c);
printf("%lld", f(r,c)%100000000); 함숫값을 100000000으로 나눈 값 출력
}
완벽한 코드!인 것처럼 보이지만, 이 방법은 너무나 naive(순진)한 방법이다. 이 코드를 그대로 제출하면 바로 시간초과가 나기 때문이다. 어떻게 해야 시간 복잡도를 줄일 수 있을까? 이전 시간에 소개한 메모이제이션 기법을 사용하면 간단하게 해결할 수 있다. 간단하게 설명하자면, 이 코드에서 시간 복잡도가 높아지는 이유는 같은 연산을 여러 번 반복하기 때문이다. 따라서, 여러번 쓸 값을 변수에 저장해두고 필요할 때 꺼내쓰는 것이 메모이제이션 기법이다.
#include <stdio.h>
int memo[100][100]= {}; // 저장할 값의 개수가 아주 많고, 2차원으로 표현되므로 2차원 배열을 선언한다.
long long f(int m, int n)
{
if(m<=0 || n<=0) return 0;
else if(memo[m][n]!=0) return memo[m][n]; // 이미 저장된 값이 존재한다면, 연산을 거치지 않고 바로 불러옴
else if(m==1 || n==1) return memo[m][n] = 1; // 배열에 값을 저장하면서 값을 반환한다
else return memo[m][n] = (f(m-1,n) + f(m,n-1))%100000000; // 배열에 연산한 값을 저장하면서 값을 반환함
}
int main()
{
int r,c;
scanf("%d %d", &r, &c);
printf("%lld", f(r,c)%100000000);
}
이렇게 제출하면 시간 초과가 발생하지 않는다.
배열을 하나 선언해서 자주 쓸 값을 저장하는 것 만으로도 시간을 크게 절약할 수 있다.
오늘도 코딩이다.