Computer Science/알고리즘
[정올] 자리배치 (문제번호 : 2098)
GOD동하
2020. 2. 14. 09:14
http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1361&sca=5040
JUNGOL | 자리 배치 > 문제은행
어떤 극장의 자리는 한 줄로 배치되어 있고 자리번호는 왼쪽부터 1에서 N까지 차례대로 매겨져 있다. 이 N개의 자리 중에서 N-1개의 자리는 지정석으로 모두 판매하고, 어떤 한 자리만 자유석으로 비워둔다. 지정석 표를 산 사람들은 아래 규칙에 따라서만 앉을 수 있다. 규칙) 사람들은 구입한 지정석 표에 적힌 번호의 자리에 앉든지, 그 자리의 바로 왼쪽이나 오른쪽의 인접한 자리에 앉든지, 또는 자유석에 앉을 수 있다. 예를 들어 설명해보자. 4개의 자리가
www.jungol.co.kr
자유석을 기준으로 왼쪽 오른쪽으로 나누는 것이 포인트
두가지 케이스가 나오는데
1) 자유석을 포함하는 왼쪽 + 자유석이 없는 오른쪽
2) 자유석이 없는 왼쪽 + 자유석을 포함하는 오른쪽
여기서 두 케이스 다 자유석에 아무도 앉히지 않을 경우가 겹치므로 제외
경우의수는 하다보니까 피보나치를 이용하는 규칙이 발견됨
(나중에 그림 추가함)
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
private static long[] D;
private static int[] F;
private static int[] FD;
private static int N;
private static int K;
final private static int MAX = 40;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
F = new int[MAX+1];
FD = new int[MAX+1];
D = new long[MAX+1];
initF();
initFD();
initD();
int L = K;
int R = N-K;
// 자유석 기준으로 왼쪽 오른쪽 분할해서 생각
// 두가지 경우가 나오는데
// 왼쪽에 자유석이 포함될 경우 => D[L] * F[R]
// 오른쪽에 자유석이 포함될 경우 => D[R+1] * F[L-1]
// 이 두가지 케이스 더해서 자유석에 아무도 앉지 않을 경우가 중복되므로 제외 => F[L-1] * F[R]
long res = K==1 || K==N ? D[N] : (D[L] * F[R] + D[R+1] * F[L-1] - F[L-1] * F[R]);
bw.write(String.valueOf(res));
bw.flush();
bw.close();
}
// 자유석이 없는 경우를 생각할 때
// i 번을 지정석에 앉힐 경우의 수
// i-1 번을 앞에 앉힐 경우의 수
// 두 확률이 계속 더해지므로 피보나치 수열이 됨
private static void initF() {
F[0] = F[1] = 1;
for (int i = 2; i <= MAX; i++) {
F[i] = F[i-1] + F[i-2];
}
}
private static void initFD() {
FD[1] = 1; // FD[N] = 피보나치 N까지의 합
for (int i = 2; i <= MAX; i++) {
FD[i] = FD[i-1] + F[i];
}
}
private static void initD() {
D[1] = 1;
D[2] = 1 + 0 + 1;
for (int i = 3; i <= MAX; i++) {
D[i] = D[i-1] + D[i-2] + FD[i-1];
}
}
}