취미로 코딩하기

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

이번에 볼 문제는 백준 3948번 문제인 홍준이의 친위대이다.
문제는 아래 링크를 확인하자.

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

1부터 20까지의 alternating permutation의 개수를 구하는 문제이다.

incr[i][j]를 숫자 j를 첫 숫자로, 증가하는 것으로 시작하는 순열의 개수라 하고, decr[i][j]를 숫자 j를 첫 숫자로, 감소하는 것으로 시작하는 순열의 개수라 하자.

이 때 incr[i][j]는 i보다 큰 수로 시작하면서 감소하는 이어질 수 있는 순열의 개수, decr[i][j]는 i보다 작은 수로 시작하면서 증가하는 이어질 수 있는 순열의 개수와 같다는 점을 이용하여 점화식을 세울 수 있다.

위 점화식을 이용하여 문제를 해결해보자.

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

#include<iostream>
using namespace std;
typedef long long ll;

ll incr[21][21], decr[21][21];
ll ans[21];

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

	incr[2][1] = decr[2][2] = 1;

	for (int i = 3; i <= 20; i++) {
		for (int j = 2; j <= i; j++) {
			decr[i][j] = decr[i][j - 1] + incr[i - 1][j - 1];
		}
		for (int j = i - 1; j >= 1; j--) {
			incr[i][j] = incr[i][j + 1] + decr[i - 1][j];
		}
	}

	ans[1] = 1;
	for (int i = 2; i <= 20; i++) {
		for (int j = 1; j <= i; j++) ans[i] += incr[i][j];
		for (int j = 1; j <= i; j++) ans[i] += decr[i][j];
	}

	int T; cin >> T;
	while (T--) {
		int x; cin >> x;
		cout << ans[x] << '\n';
	}
}