[C++] 백준 13699번 점화식

1. 문제이해

13699번: 점화식 (acmicpc.net)

13699번: 점화식

 

아래와 같은 점화식에 의해 정의된 수열 t(n)이 있다.

t(0) = 1;

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

n이 주어질때, t(n)의 값을 출력하는 프로그램을 구현하는 것이 목표이다.

 

 

 

2. 문제풀이

 

문제에 나와있는 점화식을 그대로 활용해 코드를 구현하면 되는 간단한 문제이다.

 

문제에서 준 점화식은 t(n) = t(0) * t(n-1) + t(1) * t(n-2) + ... + t(n-1) * t(0) 으로,

변수 2개를 두어 하나는 0, 1, 2, 3, ..., n-1 까지 증가하고,

하나는 n-1, n-2, n-3, ..., 0 까지 감소하도록 설정해 식을 세우면 된다.

 

한가지 주의할 점은 바로 범위인데,

예제 입력 2의 경우인 25를 보면, 출력이 4861946401452로,

int형을 벗어나는 범위를 출력하게 된다.

따라서, long long 형을 사용해 알맞은 결과를 출력하도록 했다.

 

 

 

3. 소스코드

#include <iostream>
using namespace std;

int main() {
	int N;

	// 배열 내 값들을 0으로 초기화
	// 0으로 초기화해주지 않으면 올바른 값 출력 X
	long long TN[35] = { 0, };

	cin >> N;

	TN[0] = 1;

	for (int i = 1; i < N + 1; i++) {
		for (int j = 0; j < i; j++) {
			// 문제의 점화식 그대로 이용
			TN[i] += TN[j] * TN[i - j - 1];
		}
	}

	cout << TN[N];

	return 0;
}

N의 범위가 0부터 35까지이므로, 크기가 35인 long long 형 배열을 선언해주었다.

해당 TN은 점화식 t(n)의 값들을 저장하도록 해주었다.

for문을 거치기에 앞서, 해당 배열의 값들을 모두 0으로 초기화해주어 오류를 방지했다.

(0으로 초기화해주지 않으면 쓰레기값이 들어가게 되어 올바른 값이 출력되지 않았다.)

 

이후 N을 입력받고, 이중 for문을 통해 문제에서 주어진 점화식을 코드로 구현했다.

 

 

---

오늘도 어김없이 다이나믹 프로그래밍 문제를 풀어보았다.

DP문제는 일단 쉬운 문제부터 풀어보고 있는데, 오늘은 어렵지 않았지만,

조금만 어려워도 머리가 아파오기 시작한다..ㅎㅎ😱

열심히 코드짜봐야지..🐜