링크

문제 요약

문제의 상황을 요약해보면, 카톡 단체 채팅에서 안 읽은 사람의 수를 나타내는 숫자가 입력으로 주어졌을 때, 그런 상태를 만들 수 있는 경우의 수를 구하라는 문제이다.

관찰

문제에서 두 경우의 수가 다르다는 뜻은, 각 메시지 별로 읽은 사람의 집합이 다름을 의미한다. 이때 문제의 규칙에 의해 실질적으로 가장 중요한 정보는 각 사람별로 접속을 했는지 여부와, 만약 접속을 했다면 그 사람이 마지막으로 읽은 메시지의 위치(=접속 종료 시점)가 중요하다. 따라서 사람별로 이를 결정하면 문제에서 구하고자 하는 경우의 수를 구할 수 있을 것이다.

풀이

가장 직관적으로 불가능한 경우의 수부터 제거하도록 하자. 각 메시지 별로 읽은 사람의 수 $(A_i)$ 를 순서대로 나열하면, 이 수열은 절대로 증가할 수가 없다. 따라서 증가하는 경우가 존재한다면 정답은 0이 된다. 다음으로는 메시지를 읽은 최소한의 집합을 생각해보도록 하자. 메시지를 읽은 최소한의 집합이란, 채팅을 치지 않은 사람들은 메시지를 아무도 읽지 않았고, 채팅을 친 사람들은 자신의 메시지를 작성 후 바로 접속을 종료한 경우를 의미한다. 이는 각 사람별로 마지막으로 작성한 메시지 번호를 기록하여 쉽게 계산이 가능하고 이 수열을 $(B_i)$ 라고 하자.

지금까지 우리는 단순히 메시지를 읽은 사람의 수를 가지고 불가능 여부를 확인하였고, 메시지를 읽은 최소한의 집합을 구하였다. 이렇게 두 수열 값을 가지고 문제를 해결할 수 있는데, 자명히 불가능한 경우가 존재한다. 바로 읽은 사람의 수가 메시지를 읽은 최소한의 집합보다 작은 경우이다. 즉, 수식으로 나타내면 $A_i<B_i$ 인 경우가 존재한다면, 이는 불가능한 경우이고 답은 0이다.

이렇게 불가능한 경우를 제거하면 이제는 무조건 조건을 만족하는 경우의 수가 1가지 이상 존재한다. 일단 각 수열을 좀 더 명확하게 정의하도록 하자.

$A_i=i$번째 메시지를 보낸 이후의 읽은 사람의 수
$B_i=i$번째 메시지를 보내기 직전 시점에서 메시지를 읽은 최소한의 집합에 포함된 사람의 수
편의상 $A_0=N$, $B_0=N$ 라고 하자.

문제의 조건을 만족하는 경우의 수를 만든다는 것은, 메시지를 읽은 최소한의 집합을 기준으로 만둘 수 있다. 현 시점에서 본 집합에 속한 사람들은 절대로 이번에 접속 종료를 해서는 안 되기 때문에, 이 사실을 염두에 두고 각 사람별 종료 시점을 결정하면 경우의 수를 계산할 수 있다.

만약 현시점 $i$ 에서 $A_i\neq{A_{i+1} }$ 가 성립한다면, $A_i-A_{i+1}$ 만큼의 인원이 $i$ 번 메시지를 마지막으로 읽고 접속을 종료해야 함을 의미한다. 또한 이번에 접속을 종료해서는 안되는 사람$(=B_{i+1})$ 을 제외하고, 나머지 인원 중에 뽑아야 하므로 현 시점의 접속한 인원 수$(=A_i)$ 에서 해당 값을 빼야 한다. 따라서 $\displaystyle { { A_i-B_{i+1} } \choose { A_i-A_{i+1} } }$ 가지 만큼 접속 종료 인원을 뽑는 경우의 수가 존재한다.

결론적으로 각 시점별로 접속 종료 인원을 결정해야 되는 순간마다 저 식을 곱해주면 정답을 구할 수 있다. 이를 효율적으로 하기 위해서는 팩토리얼 값과, 그 값의 잉여 역수 값을 미리 전처리 해두면 된다. 그 과정은 구현에 따라 다르지만 대개 선형 시간에 해결이 가능하고, 경우의 수를 계산하는 과정도 자명히 선형 시간이므로, 전체 시간 복잡도는 $O(N+M)$ 에 문제가 해결된다.