아파트 경우의 수(DP)

public class Main {
    public static void main(String[] args) throws Exception {
        System.out.println(apt(8));
    }
    
    static long apt(int n){
        long[] dp = new long[n+3];
        dp[1] = 1;
        dp[2] = 1;
        for(int i=3;i<=n+2;i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n+2];
    }
}

package basic.dp;

import java.util.Arrays;

// 이전 단계보다 더 늘어나는 수는, 이전 단계의 노란색의 수만큼 늘어난다. (노랑->파랑, 노랑->노랑 효과)
// 이전 단계의 노란색의 수는? => 한단계 더 이전 단계의 수 <= 한단계 더 이전 단계의 수 모두에 노란색을 사용할 수 있다

public class 아파트색칠하기 {

	static int memoi[] = new int[9]; // 0 는 dummy
	public static void main(String[] args) {
		memoi[1] = 2;
		memoi[2] = 3;
		
		for (int i = 3; i <= 8; i++) {
			memoi[i] = memoi[i-1] + memoi[i-2];
		}
		
		System.out.println(memoi[8]);
		System.out.println(Arrays.toString(memoi));
	}

}