[Java] 프로그래머스 [Level-4] 쌍둥이 빌딩 숲

public class Solution {
	
	// 쌍둥이 빌딩 숲
	// 전체 쌍둥이 빌딩의 수, 측면에서 봤을 때 보이는 빌딩의 수 [경우의 수]
	// 가장 높은 쌍둥이 빌딩부터 순서대로 배치
	// 1, 1 = 11 [1개]

	// 2, 1 = 1221, 1122 [2개] 1 * 2
	// 2, 2 = 2211 [1개] 1
	
	// 3, 1 = 133221, 123321, 122331, 122133, 133122, 113322, 112332, 112233 [8개] 2 * 4
	// 3, 2 = 233211, 223311, 221331, 221133, 331221, 331122 [6개] 1 * 4 + 2
	// 3, 3 = 332211 [1개] 1
	
	// 4, 1 = [48개] 8 * 6
	// 4, 2 = [44개] 6 * 6 + 8
	// 4, 3 = [12개] 1 * 6 + 6
	// 4, 4 = [1개] 1
	
	// 5, 1 = [384개] 48 * 8
	// 5, 2 = [400개] 44 * 8 + 48
	// 5, 3 = [140개] 12 * 8 + 44
	// 5, 4 = [20개] 1 * 8 + 12
	// 5, 5 = [1개] 1
	
	// (x, y)를 전체 쌍둥이 빌딩 x개 중, 측면에서 봤을 때 y개의 빌딩이 보이는 경우의 수라고 했을 때
	// (1, 1)은 1로 고정
	// x는 2 이상이고, y가 1일 때 (x, y)를 만드는 방법 => (x, y) = (x - 1, y) * (2 * (x - 1))
	// x는 2 이상이고, y가 1보다 크고 x보다 작을 때 (x, y)를 만드는 방법 => (x, y) = (x - 1, y) * (2 * (x - 1)) + (x - 1, y - 1)
	// x는 2 이상이고, y가 x일 때 (x, y)를 만드는 방법 => (x, y) = (x - 1, y - 1)
	
	// 11 (가장 높은 쌍둥이 빌딩 11 배치)
	// ☆☆ 1 ☆☆ 1 ☆☆ (다음으로 높은 쌍둥이 빌딩 배치할 위치 찾기)
	// 22 11 (다음으로 높은 빌딩 22를 제일 앞에 배치 시 보이는 건물 + 1, 경우의 수는 배치 전 그대로)
	// 1 22 1, 11 22 (다음으로 높은 빌딩 22를 빌딩 사이 또는 제일 뒤에 배치 시 보이는 건물 그대로, 경우의 수는 배치 전 * 2
	// 다음으로 높은 빌딩 33을 제일 앞에 배치 시 => 보이는 건물 + 1, 경우의 수는 배치 전 그대로
	// 2211(하나의 예) => 332211
	// 다음으로 높은 빌딩 33을 빌딩 사이 또는 제일 뒤에 배치 시 => 보이는 건물 그대로, 경우의 수는 배치 전 * (2 * (배치 후 쌍둥이 빌딩의 수 - 1))
	// 2211(하나의 예) => 233211, 223311, 221331, 221133
	
	// 3, 1의 경우의 수는 2, 1의 경우의 수에서만 생각 (2, 2는 이미 빌딩 2개가 보이는 상태)
	// 2, 1이 3, 1이 되기 위해서는 쌍둥이 빌딩 한 쌍을 추가로 배치하면서 보이는 건물은 그대로여야 한다. => 사이 또는 제일 뒤에 배치
	// 2, 1의 경우인 1221, 1122 경우의 수 2에 * (2 * (3 - 1)) => 3, 1 = 8개
	// 3, 2의 경우의 수는 2, 2의 경우의 수에서 사이 또는 제일 뒤에 배치, 2, 1의 경우의 수에서 제일 앞에 배치 (2가지 경우가 존재)
	// 2, 2의 경우인 2211 경우의 수 1에 * (2 * (3 - 1)) => 4
	// 2, 1의 경우인 1221, 1122 경우의 수 2 그대로
	// 3, 2 => 6개
	// 3, 3의 경우의 수는 2, 2의 경우의 수에서만 생각, 제일 앞에 배치 => 2, 2의 경우인 2211 경우의 수 1 그대로 (332211)
	
	public static int solution(int n, int count) {
		long[][] arr = new long[n + 1][n + 1];
		long preventOutOfRange = 1000000007;
		long temp = 0;
		
		arr[1][1] = 1;
		
		for (int x = 2; x <= n; x++) { // x는 2 이상
			
			for (int y = 1; y <= x; y++) {
				
				if (y == 1) { // y가 1일 때 arr[x][y]를 만드는 방법 => arr[x][y] = arr[x - 1][y] * (2 * (x - 1));
					temp = arr[x - 1][y] * (2 * (x - 1));
				} else if (y > 1 && y < x) { // y가 1보다 크고 x보다 작을 때 arr[x][y]를 만드는 방법 => arr[x][y] = arr[x - 1][y] * (2 * (x - 1)) + arr[x - 1][y - 1];
					temp = arr[x - 1][y] * (2 * (x - 1)) + arr[x - 1][y - 1];
				} else { // y가 x일 때 arr[x][y]를 만드는 방법 => arr[x][y] = arr[x - 1][y - 1];
					temp = arr[x - 1][y - 1];
				}
				
				arr[x][y] = temp % preventOutOfRange;
			}
		}
		
		return (int) arr[n][count];
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 3;
		int count = 1;
		
		System.out.println(solution(n, count)); // 8
	}
}

(x, y)를 전체 쌍둥이 빌딩 x개 중, 측면에서 봤을 때 y개의 빌딩이 보이는 경우의 수라고 했을 때

(1, 1)은 1로 고정

x는 2 이상이고, y가 1일 때 (x, y)를 만드는 방법

=> (x, y) = (x - 1, y) * (2 * (x - 1))

x는 2 이상이고, y가 1보다 크고 x보다 작을 때 (x, y)를 만드는 방법

=> (x, y) = (x - 1, y) * (2 * (x - 1)) + (x - 1, y - 1)

x는 2 이상이고, y가 x일 때 (x, y)를 만드는 방법

=> (x, y) = (x - 1, y - 1)

프로그래머스 쌍둥이 빌딩 숲 문제 풀이 Java