AOJ1011 Finding the Largest Carbon Compound Given Its Longest Chain

AOJ Volume10

問題リンク Finding the Largest Carbon Compound Given Its Longest Chain

  • 概要

炭素だけを結合した化合物の構造の中で、最大鎖長がNであるようなもののうち、炭素の数の最大を求めよ
1 <= N <= 30

  • 解法

Nの偶奇で場合分けすると、炭素の最大数の増え方の規則が見えてきます。
偶奇のどちらの場合も、中心の炭素から伸ばしていく考え方をすると考えやすいです。

（長い間ずっと、最大鎖長がNになるような異性体は何種類あるかという問題だと思ってました）

  • ソース
import java.util.Scanner;

//Finding the Largest Carbon Compound Given Its Longest Chain
public class AOJ1011 {

	void run(){
		Scanner sc = new Scanner(System.in);
		int[] dp = new int[31];
		dp[1] = 1;
		dp[2] = 2;
		int sum = 0;
		for(int i=3;i<=30;i+=2){
			sum+=Math.pow(3, (i-3)/2);
			dp[i] = 1+4*sum;
		}
		sum = 0;
		for(int i=4;i<=30;i+=2){
			sum+=Math.pow(3, (i-4)/2);
			dp[i] = 2+6*sum;
		}
		while(sc.hasNext())System.out.println(dp[sc.nextInt()]);
	}
	
	public static void main(String[] args) {
		new AOJ1011().run();
	}
}