[C]백준_13699 : 점화식

출처

https://www.acmicpc.net/problem/13699

---

문제

다음의 점화식에 의해 정의된 수열 t(n)을 생각하자:

• t(0)=1
• t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0)

이 정의에 따르면,

• t(1)=t(0)*t(0)=1
• t(2)=t(0)*t(1)+t(1)*t(0)=2
• t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5
• ...

주어진 입력 0 ≤ n ≤ 35에 대하여 t(n)을 출력하는 프로그램을 작성하시오.

---

입력

첫째 줄에 n (0 ≤ n ≤ 35)이 주어진다.

---

출력

첫째 줄에 t(n)을 출력한다.

---

예제 입출력

---

알고리즘 분류

• 다이나믹 프로그래밍

---

➡️문제 분석

점화식이란?
수열의 항(項) 사이에 성립하는 관계식

문제에서 주어진 점화식을 보면,
t(n) = t(0)*t(n-1) + t(1)*t(n-2) + ... + t(n-1)*t(0)

*을 기준으로 앞의 식은 t(0)부터 t(n-1)까지
뒤의 식은 t(n-1)부터 t(0)까지 증가하고 감소하는 규칙이 있다.

---

➡️코드(⭕)

#include <stdio.h>

int main()
{
	int i, j, n;
	long long t[36] = { 0 };

	scanf("%d", &n);

	t[0] = 1;

	for (i = 1; i < n + 1; i++)
	{
		for (j = 0; j < i; j++)
		{
			t[i] += t[j] * t[i - j - 1];
		}
	}
	printf("%lld\n", t[n]);

	return 0;
}

---

➡️코드 분석

1. 예제 출력 2를 보면 int형 범위(~2,147,483,647)를 벗어나는 값이므로 t배열을 long long형으로 선언해주고, 크기는 n(0 ≤ n ≤ 35)이므로 36으로 설정해준다.

2. n을 입력받고, t[0]은 예외로 값을 1로 지정해준다.

3. 이중 for문을 이용하여 i는 1부터 n까지, j는 0부터 n-1까지 반복한다.

   t[1] = t[0] * t[1-0-1]
   t[2] = t[0] * t[2-0-1] + t[1] * t[2-1-1]
   t[3] = t[0] * t[3-0-1] + t[1] * t[3-1-1] + t[2] * t[3-2-1]
   ...

4. 배열 t는 long long형이므로 %lld 형태로 t[n]을 출력한다.

---

✍️피드백

int i, j, n;

이렇게 반복문에 사용할 변수 i와 j를 위에서 미리 선언하는 것은 좋지 않다!!!

for (int i = 1; i < n + 1; i++)

위 처럼 해당 for문 안에 지역 변수로 선언해주는 것이 좋다.

미리 선언해줄 경우 for문 안에서만 쓰이는 i의 값이 다른 코드에 영향을 줄 수도 있기 때문!

---

➡️end

이중 for문 안의 식이 이해는 가지만 내가 직접 식을 세우기엔 아직 어려운 것 같다..

헐!! 예전에 for문 안에서 변수를 선언하는 것이 안좋다고 해서 일부러 불편해도 위에서 선언해줬는데... 저렇게 하는건 엄청 옛날 방식이라고 한다..
앞으론 필요한 곳에서 따로 선언해야겠다!