[C]백준_13699 : 점화식

2022년 11월 29일에 작성됨

 

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

13699번: 점화식

 

 

문제 분석

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

문제에서 주어진 점화식을 보면,
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문 안에서 변수를 선언하는 것이 안좋다고 해서 일부러 불편해도 위에서 선언해줬는데... 저렇게 하는건 엄청 옛날 방식이라고 한다..
앞으론 필요한 곳에서 따로 선언해야겠다!