CodeUp / Recursion(재귀) / 3702번 / 파스칼의 삼각형2 / C++

 

문제 설명  

다음과 같은 삼각형을 파스칼의 삼각형이라고 한다.

 

회전 변환된 이 삼각형에서 (r행, c열)의 값을 알 수 있는 프로그램을 작성하시오. 행과 열은 1부터 시작한다.

 

입력

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

 

출력

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

 

입력 예시

3 2

 

출력 예시

3

 

#include <iostream>
using namespace std;

int arr[50][50] = { 0 };

int pascal(int r, int c) {
    if(r == 1 || c == 1) // 1행과 1열은 모두 1이므로 1을 저장한다
        arr[r][c] = 1;
        
    if(arr[r][c]) // 만약 배열에 이미 저장되있을경우 그 값을 return(메모이제이션)
        return arr[r][c];
        
    arr[r][c] = (pascal(r, c - 1) + pascal(r - 1, c)) % 100000000;
    
    return arr[r][c];
}

int main() {
    int r, c;
    cin >> r >> c;
    
    cout << pascal(r, c) << endl;
}

---

여기서 가장 중요했던 것은 pascal 함수 위에 return문 바로 위에있는 줄이 아닌가싶다.

처음엔 어떻게 해야하지 막막했다.

그래서 재귀함수가 되려면 규칙성이 있어야하니, 그 규칙성을 찾기로했다.

눈으로만 보면서 하기엔 헷갈려서 써내려가면서 하니 규칙성이 보였다.

만약 우리가 2행 3열을 구하고자 한다면, 2행 2열과 1행 3열을 더해야한다.

간단하게 나타내면, (2, 3) = (2, 2) + (1, 3) 이다.

이것을 공식으로 나타내보자면, (r, c) = (r, c-1) + (r-1, c) 이다.

이것만 캐치해낸다면, 손쉽게 코드를 작성할 수 있다.