[BOJ 26948 // C++] Plankan

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 26948번 문제인 Plankan이다.
문제는 아래 링크를 확인하자.

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

26948번: Plankan

길이 N(N>2)의 막대는 마지막에 길이 1의 막대가 붙어 완성되거나 길이 2의 막대가 붙어 완성되거나 길이 3의 막대가 붙어 완성되는 세 종류로 분류할 수 있다. 마지막에 길이 1의 막대가 붙어 완성될 경우의 수는 길이 N-1의 막대의 가짓수와 같고, 마지막에 길이 2의 막대가 붙어 완성될 경우의 수는 길이 N-2의 막대의 가짓수와 같고, 마지막에 길이 3의 막대가 붙어 완성될 경우의 수는 길이 N-3의 막대의 가짓수와 같음을 눈여겨보자.

 

위의 관찰을 이용해 길이 N의 막대를 만드는 경우의 수를 구하는 점화식을 세워 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;
int dp[25];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	dp[0] = 1, dp[1] = 1, dp[2] = 2;
	for (int i = 3; i < 25; i++) dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];

	cin >> N;
	cout << dp[N];
}