• 백준 2302번 극장 좌석 [DP] :: 마이구미
    알고리즘 풀이/동적계획법 2017. 2. 25. 22:59
    반응형

    이번 글은 백준 알고리즘 2302번 "극장 좌석" 문제를 다뤄본다.

    이 문제의 키워드는 동적계획법(DP), 피보나치, 곱의 법칙이다.

    문제를 보자.


    어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 써 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.


    그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.


    한 좌석을 기준으로 왼쪽 1칸이나 오른쪽 1칸으로 VIP 좌석이 아닌 좌석으로 이동할 수 있다.

    이 문제는 곱의 법칙을 활용할 수 있다.


    중등 수학에서 나오는 법칙으로써, 합의 법칙과 곱의 법칙이 존재한다.

    합의 법칙과 곱의 법칙은 경우의 수를 구하는 방법이다.


    합의 법칙은 두 사건 A, B가 있을 때, 동시에 일어나지 않았을 경우 두 사건의 경우의 수를 각각 더한다.

    곱의 법칙은 두 사건 A, B가 있을 때, 동시에 일어날 경우 두 사건의 경우의 수를 곱한다.

    자세한 건 관련 링크를 참고하자.




    VIP 좌석이 4, 7이 주어졌을 경우, 위와 같이 {1,2,3} , {5,6}, {8,9} 의 경우가 나온다.

    이 경우들이 동시에 일어나기 때문에 각각 곱해주면 정답을 구할 수 있다.


    점화식은 어떻게 구할 수 있을까?

    하나의 좌석을 기준으로 좌석을 옮기는 경우는 2가지다.

    1. 좌석을 옮기는 경우. - dp[n-2]

    2. 좌석을 옮기지 않는 경우. - dp[n-1]

    이를 활용하여 점화식 dp[n] = dp[n-1] + dp[n-2]  만들 수 있다.


    정확한 이해를 위해서는 직접 경우의 수를 만들어보면 된다.


    극장 좌석 예시


    위 그림을 보자.

    n = 2 의 경우 2가지

    n = 3 의 경우 3가지

    n = 4 의 경우 5가지

    계속해서 구해보면 n = 5 의 경우는 8가지... 피보나치 수열을 볼 수 있다.


    n = 3의 경우에서 4를 붙여보면 n = 4의 경우 중 3가지를 포함하는 것을 볼 수 있다.

    4를 붙인다는 것은 좌석을 옮기지 않는 경우를 뜻한다.

    나머지 2가지는 n = 2인 경우 좌석을 옮기는 경우가 된다.

    위 그림에서 이어진 선들을 보면 이해가 갈 것이다.



    극장 좌석 예시


    for(int i=2;i<=n;i++) { dp[i] = dp[i-1] + dp[i-2]; } int tmp = 0; for(int i=0;i<m;i++) { int k = sc.nextInt(); ans *= dp[k-tmp-1]; tmp = k; } ans *= dp[n - tmp];


    전체 소스는 아래 Github URL을 통해 확인하길바란다.


    백준 알고리즘 2302번 문제 "극장 좌석" 전체 소스

    https://github.com/hotehrud/acmicpc/blob/master/dp/2302.java

    반응형

    댓글

Designed by Tistory.