블로그 옮겼습니다

BOJ 12872번 플레이 리스트 본문

Algorithm/Problem Solving

BOJ 12872번 플레이 리스트

sgc109 2017. 2. 18. 11:30

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


1<=N<=100

0<=M<=N

N<=P<=100 인

N,M,P 가 주어지는데 N가지의 곡이 있고 이 곡들을 바탕으로 P개의 곡으로 구성된 플레이 리스트를 만드는 경우의 수를 구하는 문제다. 다만 두 가지 조건을 만족 하는 플레이 리스트 여야한다.


1. 같은 두 곡 사이에는 M개 이상의 다른 곡이 있어야 한다. 즉, 플레이 리스트에 이미 추가 했던 곡을 다시 추가하려면 마지막으로 추가한 위치와 새로 추가하려는 위치 사이에는 적어도 M개의 곡이 있어야 한다.


2. 모든 종류의 곡이 적어도 한 번씩은 플레이리스트에 포함되어야 한다.



이 문제는 N 종류의 원소를 특정 조건에 맞게 P번 선택하는 문제이다.(중복원소선택가능)

가장 간단한 모든 경우를 다 따져 주는 방법은 O(N^P) 이다. 하지만 너무 오래걸린다.


이럴때 보통 0<=pos<P 인 pos가 점화식의 첫번째 변수가 될텐데 나머지 변수는

꼭 특정 변수를 가리키는 것이 아니어도 된다. 달리 말하면 pos 번째에 N 종류의 원소들 중 한가지를 놓는 각각의 경우를 따져주지 않고, 그냥 어떤 덩어리에 포함된 원소중 아무거나 한개를 놓는경우를 한꺼번에 묶어서 계산해주면 된다. 특정 위치에 실제로 어떤 종류를 놓았는지는 전혀 알 필요가 없기 때문이다. 묶어서 계산한다는 것은 가능한 선택지의 수를 곱하는 연산을 하는 것을 말한다.


이 문제에서는 이미 놓은 종류의 수와 아직 놓지 않은 종류의 수로 점화식을 정의하는데 각각의 부분문제에서 이미 놓은 종류의 집합에서 아무거나 한개를 다시 놓거나 아직 놓지 않은 종류의 집합에서 아무거나 한개를 새로 놓거나 둘중 한가지의 판단을 하면된다. 물론 첫번째 조건때문에 이미 놓은 종류는 못놓을 때도있다. 하지만 아직 놓지 않은 종류는 무조건 놓을 수 있다. 왜냐하면 아직 한번도 놓지 않았으면 사이에 다른곡이 몇개가있는 지 볼 필요가 없기 때문이다. (한개로는 '사이' 라는게 생기지도 않기 때문)

여기서 중요한것은 '어떤 집합에서 아무거나 하나를 놓으면 된다'='어떤 집합의 원소의 수를 곱한다' 라는 것이다. 그리고 특정 종류의 원소를 선택했을 때 집합의 변화가 있는지를 고려해 주면된다. 만약 변화가 있다면 수정해주면되는것이다.


그래서 부분 문제 D 의 정의와 점화식은 이렇게 나온다.


D(n, sel) = 플레이 리스트에 맨 처음부터 n개의 곡을 추가했고, sel개의 종류의 곡을 이미 플레이 리스트에 한 곡이상 추가했을 때의 경우의 수.


D(p,sel) = (N-sel+1) * D(p-1,sel-1) + (sel-M) * D(p-1,sel)(if, sel>M)


점화식의 첫번째 항은 아직까지 플레이 리스트에 포함 되지 않은 곡을 처음으로 새로 추가 하는것을 나타낸것이고, 두번째 항은 기존에 플레이 리스트에 한번 이상 포함되어있는 곡을 다시 추가하는 것을 나타낸것이다.

점화식에서 두번째 항을 보면 뒤에 if, sel>M 라는 조건이 달려있는데 이 이유는 이 문제의 두번 째 조건 때문인데 같은 종류의 두 곡 사이에는 적어도 M개의 곡이 있어야 하기 때문에 전체 플레이 리스트에서 M개의 연속된 부분 리스트는 무조건 모두 서로 다른 종류의 곡들로 구성 되어있어야한다. 그렇기 때문에 아직 전체 플레이 리스트가 M개도 되지 않았는데 다시 이미 추가된 종류의 곡을 추가할 수는 없는 것이다.

점화식의 첫번째 항은 아직 플레이 리스트에 한번도 포함 되지 않은 곡을 처음으로 새로 추가하는 것이기 때문에 아직 선택하지 않은 곡이 한개라도 있다면 아직 선택하지 않은 unsel가지 중 한가지를 선택하여 플레이 리스트에 추가하는것은 무조건 가능하고, 두번 째 항은 마지막 M개의 곡(연속된 M개의 곡은 모두 달라야 하기 때문에 '마지막 M개의곡'='마지막 M가지의 곡' 이다.) 을 제외한 종류라면 이미 플레이 리스트에 추가된 종류의 곡이라도 다시 놓을 수가 있는것이다. 그렇기 때문에 기존에 선택한 종류의 곡중에는 sel-M 가지 중 한가지를 선택할 수 있는 것이다.




+그리고 백준님 강의 때 들은 것인데, dp 문제에서 특정 조건이 주어지면 그 조건 자체가 점화식의 일부 항이 되는 경우가 많나 보다.


우선, 보통 P개를 선택해야하면 점화식의 첫번째 항은 p(0<=p<=P)이고

이 문제의 두번째 조건을 보면 p개를 플레이 리스트에 추가했을 때 몇가지 종류의 곡이 플레이 리스트에 포함되어 있는지를 알아야 하는데 점화식의 sel 이 바로 그것이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
const int MOD = 1e9+7;
long long dp[101][101];
int N,M,P;
int main() {
    scanf("%d%d%d",&N,&M,&P);
    dp[0][0]=1;
    for(int i = 1; i <= P; i++){
        for(int j = 0; j <= N; j++){
            if(j > 0) (dp[i][j] += dp[i-1][j-1* (N-j+1)) %= MOD;
            if(j > M) (dp[i][j] += dp[i-1][j] * (j-M)) %= MOD;
        }
    }
    printf("%lld",dp[P][N]);
    return 0;
}
cs


Comments