BOJ-14556 Balance

필요한 지식

1. 동적계획법

접근

• 먼저 n번째 추는 1~n-번째 추들의 무게의 합보다 크다라는 점을 알아야한다.

• n+1번째 추가 놓이는 경우는 크게 2가지로 구분할 수 있다.
  1. 1~n번째 추가 놓여있고, 마지막으로 오른쪽에 놓이는 경우
  2. 마지막이 아니고 오른쪽에 놓이는 경우(n+1을 제외한 i번째 추로 끝나는 경우)

• 1번의 경우는 n+1번째 추를 놓는 경우의 수를 an+1라고 했을 때, an의 모든 경우에 오른쪽 끝에 n+1번째 추를 추가하면 되므로 an개 만큼 존재한다.

• 2번의 경우는 i 개의 추(n) X i번째 추를 제외하고 배치한 경우의 수(an) X i번째 추는 왼쪽,오른쪽 둘다 배치할 수 있으므로(2) = 2*n*an가지의 경우의 수가 있다.

• 예를들어 n+1은 3이고, i가 1이라고 하면, 1을 제외하고 2,3을 배치하는 방법의 수는 1,2를 가지고 배치하는 방법의 수와 같다. 따라서 i번째 추를 제외하고 배치한 경우의 수는 an개가 된다.

• 정리하면 n+1번째 추를 놓는 경우의 수 an+1은 (2*n+1)*an개 라는 것을 알 수 있다.

코드(C++)

#include <iostream>
using namespace std;
typedef long long ll;
int main() {
	ll n, a = 1; cin >> n;
	for (ll i = 1; i < n; i++) a = ((2 * i + 1) * a) % (int(1e9) + 9);
	cout << a;
	return 0;
}

결과