DAY1 중급 - 백준 13699번 (C++)

www.acmicpc.net/problem/13699

13699번: 점화식

 

<답안>

#include <iostream>
using namespace std;
int main()
{
    int n;
    long long array[36];
    int left,right;
    long long temp = 0;
    array[0] = 1;
    array[1] = 1;
    cin>>n;
    for(int i=2; i<=n; i++)
    {
        left = 0;
        right = i-1;
        while(left != i)
        {
            temp += array[left]*array[right];
            left++;
            right--;
        }
        array[i] = temp;
        temp = 0;
    }
    cout<<array[n];
    
    return 0;
}

 

<설명>

개인적으로 초급문제보다 쉽게? 느껴진 문제였다

t(0) = 1을 가지고서 t(1)부터 구해보면

이렇게 n=2부터 왼쪽에 곱하는 값은 0부터 n-1까지 증가, 오른쪽에 곱하는 값은 n-1부터 0까지 감소하며

누적해서 더해진 값이 n번째 값이 되는 규칙이였다

 

그러면은 35까지 입력이 되기 때문에 입력된 숫자를 인덱스로 사용하기 위해 크기가 36인 배열을 선언하였다

단, 결과값의 범위를 참고하여 long long 타입으로 선언을 하였다

 

점화식의 초기값을 array[0] = 1, array[1] = 1로 설정한 다음

입력된 값이 2이상일 경우부터 계산하였다

 

왼쪽에 곱할 인덱스를 left로 잡은다음 계산할때마다 증가를 하며 곱하고

오른쪽에 곱할 인덱스를 right로 잡은다음 계산할때마다 감소하며 곱하여

temp에 누적하여 최종적으로 구해진 temp값을 array[n]에 입력하는 식이다

 

최종적으로 array[n]을 출력한다