2302. 극장 좌석

문제 개요

한칸씩만 이동할 수 있는 좌석과 고정된 좌석이 존재할 때 가능한 모든 조합 수를 구하는 문제입니다.

문제 접근

방법의 가짓수가 최대 20억개이니 브루트 포스로는 해결할 수 없는 문제입니다. 또한 정수에 최대값이 존재하는 언어의 경우에는 이를 고려하여 타입을 설정해야 합니다. (Java의 경우에는 int)


보통 최대값이 매우 큰 문제는 수학적인 내용이 포함되어 있는 경우가 많기 때문에, 수학적으로 접근해보았습니다.


VIP에 의해 분리되는 부분들은 각각 가능한 조합을 가질 수 있습니다.
예를 들어 예제로 주어진 123456789에서 4와 7이 VIP라면 다음과 같이 3개의 부분들로 나누어질 수 있습니다.
(123) 4 (56) 7 (89)
각 부분들은 독립적이기 때문에 부분들마다 가능한 조합 수들을 모두 곱하면 가능한 모든 조합수를 구할 수 있습니다.


각 부분들의 가능한 조합수는 규칙성을 통해 발견할 수 있습니다.
길이가 1늘어날 때에는 다음 두 가지 경우의 수가 존재합니다.

1. 마지막에 추가합니다.
2. 마지막에 추가하고 바로 앞과 자리를 바꿉니다.

아래는 길이 N에 대한 가능한 조합입니다. 경우의 수를 괄호로 표기하였습니다.

N	Combination	count
1	1	1
2	12(1), 21(2)	2
3	123(1-1), 132(1-2), 213(2-1)	3
4	1234(1-1-1), 1243(1-1-2), 1324(1-2-1), 2134(2-1-1), 2143(2-1-2)	5
5	12345(1-1-1-1), 12354(1-1-1-2), 12435(1-1-2-1), 13245(1-2-1-1), 13254(1-2-1-2), 21345(2-1-1-1), 21354(2-1-1-2), 21435(2-1-2-1)	8

길이 N에 따른 조합수는 각 조합에서 마지막에 선택한 방법이 1인 경우 2개가 늘어나고 2인 경우 1개가 늘어납니다.
실제 개수를 보면 1, 2, 3, 5, 8입니다.
익숙한 패턴입니다. 피보나치 수열이죠.


결국 이 문제는 부분의 길이 N에 대한 피보나치 수들의 곱을 구하는 문제입니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.stream.IntStream;

public class Main {
    private static BufferedReader bf;
    static int N;
    static int M;
    static int[] vips;

    static void input() throws IOException{
        N = Integer.parseInt(bf.readLine());
        M = Integer.parseInt(bf.readLine());
        vips = new int[M];
        for(int i=0;i<M;i++){
            vips[i]=Integer.parseInt(bf.readLine());
        }
    }

    private static int[] fibonazzi(){
        int[] fibo = new int[45];
        fibo[0] = 1;
        fibo[1] = 1;
        fibo[2] = 2;
        IntStream.range(3, 45).forEach(idx -> {
            fibo[idx] = fibo[idx-1] + fibo[idx-2];
        });
        return fibo;
    }

    static void process(){
        int[] fibo = fibonazzi();
        int result = 1;
        int lastVip = 0;
        for(int i=0;i<M;i++){
            result *= fibo[vips[i] - lastVip - 1];
            lastVip = vips[i];
        }
        result *= fibo[N - lastVip];
        System.out.println(result);
    }

    public static void main(String[] args) throws IOException {
        bf = new BufferedReader(new InputStreamReader(System.in));
        input();
        process();    
    }

}

문제

https://www.acmicpc.net/problem/2302