[C/C++] 코드업(codeup) 3702번 파스칼의 삼각형 2

▽문제 바로가기

https://codeup.kr/problem.php?id=3702

파스칼의 삼각형 2

 

---

입력

자연수 r과 c가 입력된다. (1<=r, c<=50)

 

출력

(r, c)의 원소 값을 100,000,000으로 나눈 나머지를 출력한다.

 

문제 풀이

 

먼저 파스칼의 삼각형의 규칙을 찾아야 합니다. 파스칼의 삼각형은 1행과 1열은 모두 1이고 (r, c)는 (r-1, c)와 (r, c-1)의 합입니다. 따라서 회전 변환된 상태에서 대각선을 중심으로 대칭입니다.

 

#include <stdio.h>

int memo[51][51]={0};

int recur(int a, int b){
	if(a==1||b==1){
		//1행과 1열은 1, 여기서 부터 출발
		//메모할 필요는 없으나 메모해둠
		return memo[a][b] = memo[b][a] = 1;
	}
    
	//메모한 값이 있다면 함수호출하지 않고 메모된 값 리턴
	if(memo[a][b]!=0){return memo[a][b];}
    
	//파스칼 삼격형은, (r, c) = (r-1, c) + (r, c-1) 함수호출하면서 메모
	else{
		return memo[a][b] = memo[b][a] = (recur(a-1, b) + recur(a, b-1))%100000000;
	}
}

int main(){
	
	int a, b;
	scanf("%d %d", &a, &b);
	printf("%d\n", recur(a, b));
	
	return 0;
}