[BOJ 14556] Balance (Java)

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

14556번: Balance

import java.util.Scanner;

public class Main_BOJ_14556 {
	static int N;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		long ans=1;
		for (int i=2; i<=N; i++) {
			ans=(1L*(2*i-1)*ans)%1000000009;
		}
		System.out.println(ans);
	}

}

모르겠어서 답보고 풀었다..

 

DP+수학 문제

 

이 문제의 포인트는 2^n > (2^1+2^2+....+2^n-1) 을 이용하는 것이다.

2^1부터 2^n-1 까지 다 더해봤자 2^n 보다 작다는 사실을 이용해서 점화식을 유도한다.

A(n) //n개의 추를 썼을 때 경우의 수

-1부터 n-1까지의 추를 이용하고, 맨 마지막에 n 을 놓을 경우 이는 1가지만 가능하다. 그전에 1부터 n-1까지가 어떻게 나왔든 n을 놓는 쪽이 우승하게 되어있으므로, n은 오른쪽에만 놓을 수 있다.

-그 다음, 2~n까지의 추를 이용하고 1을 마지막에 놓는 경우..

1,3~n 까지의 추를 이용하고 2를 마지막에 놓는 경우 ..

1~n-2, n까지의 추를 이용하고 n-1를 마지막에 놓는 경우..

이 n-1가지 경우들에 대해 마지막에 놓을 수 있는 경우의 수는 2가지다. 어차피 승부처는 n을 어디에 놓았는지 따라 결정되었으므로, 왼쪽/오른쪽에 상관없이 모두 놓을 수 있는 것이다. 

 

-즉 점화식은 A(n)=A(n-1)+2*(n-1)*A(n-1)=(2*n-1)*A(n-1) 이 된다.

 

이를 이용해 N까지 답을 구해준다.