[정올] 자리배치 (문제번호 : 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];
		}
	}
}