[백준 BOJ] 13699번 점화식 (C++/cpp)

문제 설명

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

13699번: 점화식

 

접근 방법 - 다이나믹 프로그래밍(DP) 기초 문제

백준의 13699번 문제는 다이나믹 프로그래밍(DP)의 원리를 이용한 기초 문제이다.

해당 문제는, 주어진 수열의 점화식에 대하여 입력값에 대한 수열값을 출력해야 하는 문제이다.

문제에도 있는 내용이지만, 다음 수열에 대한 점화식은 아래와 같다.

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

현재까지 필자가 살펴보았을 때, 다이나믹 프로그래밍 유형은 문제의 원리를 자세히 분석하며 해결해야 하는 부류들이 대다수였기 때문에 아직 필자도 제대로 다루기가 힘든 감이 있다.

다만 이 문제와 같은 경우에는 점화식을 설명에 미리 주었기 때문에 비교적 어렵지는 않을 것으로 예상된다.

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 아래의 설명과 코드를 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 각 수열의 값을 저장할 배열(dp)을 long long int형으로 미리 선언해둔다.

(예제 입출력 중 일반적인 int형으로 표현 불가능한 숫자가 있기 때문에 long long int형으로 선언한다.)

 

2) 문제에 제시되어있는 대로, dp의 0번 값은 1로 설정해둔다.

 

3) 값(n)을 입력받는다.

 

4) 1부터 n까지 반복문을 실행하여 아래의 연산을 취한다.

- 해당 위치의 수열값을 연산하기 위해, 변수 sum을 long long int형으로 선언하며 0으로 초기화한다.

- 문제를 확인하면, 0부터 n-1까지 범위를 잡고서 양 옆으로 있는 수열값끼리 곱한 값들을 모두 합한 것을 해당 위치의 수열값으로 갖도록 하고 있다.

이를 아래처럼 반복문으로 표현하여 sum의 값에 각 곱셈의 결과들을 더하도록 한다.

for (int j = 0; j < i; j++) {
   sum += dp[j] * dp[i - j - 1];
}

- 최종적으로 연산된 sum의 값을 dp의 현재 위치 배열값에 저장한다.

 

5) 연산이 모두 완료되었다면, 그중 마지막인 dp의 n번 값을 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 13699번 코드
long long int dp[36];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	dp[0] = 1;

	int n;
	cin >> n;

	for (int i = 1; i <= n; i++) {
		long long int sum = 0;
		for (int j = 0; j < i; j++) {
			sum += dp[j] * dp[i - j - 1];
		}
		dp[i] = sum;
	}
	cout << dp[n] << endl;
}

 

제출 결과

(2022.09.17 백준 13699번 문제 제출 결과)