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
'Java > 프로그래머스' 카테고리의 다른 글
| [Java] 프로그래머스 [Level-2] 디펜스 게임 (0) | 2022.12.27 |
|---|---|
| [Java] 프로그래머스 [Level-3] 숫자 타자 대회 (0) | 2022.12.13 |
| [Java] 프로그래머스 [Level-3] 순위 (0) | 2022.11.29 |
| [Java] 프로그래머스 [Level-2] 롤케이크 자르기 (0) | 2022.11.29 |
| [Java] 프로그래머스 [Level-3] 양과 늑대 (0) | 2022.11.29 |
