문제 링크
문제
티어: 골드 1
알고리즘: dp
입력
첫 줄에는 자리의 수 N (3 ≤ N ≤ 40)이, 그 다음 줄에는 자유석의 번호 (1 ≤ K ≤ N)가 주어진다.
출력
앞서 설명한 규칙을 만족시키며 자리 배치를 할 수 있는 모든 경우의 수를 첫 줄에 출력한다. 이 값은 231-1 이하의 정수이다.
풀이
규칙을 만족시키며 자리 배치를 할 수 있는 모든 경우의 수를 출력해야 한다.
O는 자유석이며, X는 공백이라고 했을 때
1 2 3 4 O 6 7 8를 구하는 과정으로 풀이를 해보겠다.
케이스를 두 가지로 나눌 수 있다.
1. 자유석에 앉는 경우
2. 자유석에 앉지 않는 경우
1 번째 경우는 (1 2 3 4 가능한 경우의 수) * (6 7 8 가능한 경우의 수)가 된다.
그러면 1 2 3 4를 어떻게 구할 수 있을까?
-
1만 있다고 했을 때 가능한 경우의 수는 1이다.
-
1에서 2가 추가된 1 2만 있다고 했을 때는 1 2와 2 1이 가능하다.
-
1 2에서 3이 추가된 1 2 3만 있다고 했을 때는 1 2 3, 2 1 3이 가능하며 1 2 3에서 2 3은 스왑이 가능하기 때문에 1 3 2도 가능하다. 그래서 1 2 3, 2 1 3, 1 3 2 세 가지 존재한다.
여기서 알 수 있는 것은 스왑을 하기 위해서는 마지막이 2로 되어 있어야 한다.
그러면 1 2 3 경우를 구할 때 1 2에서 마지막이 2인 경우의 수 * 2 해주고, 나머지를 더해주면 되는 것이고, 마지막이 3인 경우는 곧 1 2인 경우에 3을 붙인 경우이기 때문에 1 2의 가능한 모든 경우가 된다.
정리하자면, 1 2 3을 구하기 위해서 1 2에서 마지막이 2인 경우가 필요하다. 그 경우는 1 2 딱 한 가지다. 그 외 나머지는 2 1인 한 가지이기 때문에 1 * 2 + 1로 3이 되는 것이다.
그리고 1 2 3 4를 구하기 위해서는 1 2 3에서 마지막이 3인 경우가 필요하다 이 경우는 1 2의 가능한 모든 경우가 된다. (3을 붙일 때 1 2, 2 1에 3을 붙이기 때문 그래서 1 2 3, 2 1 3)
그래서 첫 번째 케이스인 자유석이 없는 경우는 앞에 방법으로 구할 수 있다.
이를 구해놓은 배열을 dp라고 하겠다. 그래서 dp[3]인 경우는 1 2 3의 모든 경우의 수가 된다.
이번엔 두 번째 케이스인 자유석이 있는 경우를 구해야 한다.
자유석이 있다면 그 자유석에는 1, 2, 3, 4... 모든 사람이 앉을 수 있다.
그래서 우리가 구해야 하는 것은
- 자유석에 1이 앉았을 때 X 2 3 4 O 6 7 8
- 자유석에 2가 앉았을 때 1 X 3 4 O 6 7 8
...
의 합이 된다.
그럼 더 분할해서 각
X 2 3 4
1 X 3 4
1 2 X 4
1 2 3 X
은 어떻게 구할 수 있을까?
X 2 3 4부터 보면 X는 빈공간이다. 그래서 어디든 위치할 수 있다. 이게 핵심이다.
그래서 X 2 3 4인 경우는 dp[3]이 되고,
2 X 3 4는 dp[2]가 되고
2 3 X 4는 dp[1]이 된다.
여기서 마지막 2 3 X 4에서 2 3은 스왑될 수 없기 대문에 온전히 X에 오른쪽만을 계산해주면 된다. 그 값은 dp다.
그래서 각 X 2 3 4일 때 경우를 구하고 dp[3] (6 7 8)를 곱해주면 그 값은
X 2 3 4 O 6 7 8 -> 1이 자유석에 앉았을 때 모든 경우의 수가 되는 것이다.
이를 차례대로 구해서 answer에 더해주면 된다.
자세한 구현 사항은 코드를 참고해 주길 바란다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int N,K;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
K = Integer.parseInt(br.readLine());
int[] dp = new int[N + 1];
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
for(int i=3; i<=N; i++) {
dp[i] = (dp[i - 1] - dp[i - 2]) + dp[i - 2] * 2;
}
int[] dp2 = new int[N + 1]; //1 2 3 ㅁ, ㅁ 2 3 4
dp2[0] = 0;
dp2[1] = 1;
for(int i=2; i<=N; i++) {
dp2[i] = dp2[i - 1] + dp[i - 1];
}
int left = K - 1;
int right = N - K;
int answer = dp[left] * dp[right]; //자유석이 없다라고 가정했을 때
answer += cal(left, right, dp, dp2); //자유석 O
answer += cal(right, left, dp, dp2); //자유석 O
System.out.println(answer);
}
static int cal(int len1, int len2, int[] dp, int[] dp2) {
int result = 0;
for(int i=1; i<=len1; i++) {
result += (((dp2[i] * dp[len1 - i]) + (dp[i - 1] * dp2[len1 - i])) * dp[len2]);
}
return result;
}
}