1885 비부분수열
Table of Contents
접근 방법#
어떤 부분 수열을 만들 수 있나 없나를 살펴보기보다 반대로 모든 부분 수열을 만드려면 원본 수열이 어떻게 생겼는지를 생각해봐야 한다.
가령 $1, 2, 3$으로 만들 수 있는 길이가 $3$인 수열은 아래와 같다.
$$
1\ 1\ 1 \newline
1\ 1\ 2 \newline
1\ 1\ 3 \newline
… \newline
2\ 1\ 1 \newline
2\ 1\ 2 \newline
2\ 1\ 3 \newline
… \newline
3\ 3\ 1 \newline
3\ 3\ 2 \newline
3\ 3\ 3 \newline
$$
그렇다면 위에 나온 수열을 모두 부분 수열로 갖는 원본 수열은 어떤 모양일까?
첫 번째 자리에 오는 수는 $1, 2, 3$이 있으므로 수열의 앞부분에는 $1, 2, 3$이 모두 있어야 한다.
이를 다르게 생각해보면 세 개의 수 $1, 2, 3$이 한 묶음으로 존재하고 여기에서 하나를 택해 부분 수열의 첫 번째 원소를 결정한다고 할 수 있다.
그렇다면 원본 수열은 세 부분으로 나눌 수 있다.
부분 수열의 첫 번째 원소를 고를 부분,
부분 수열의 두 번째 원소를 고를 부분,
부분 수열의 세 번째 원소를 고를 부분.
그러한 수열을 아래와 같이 생각해볼 수 있다.
$$
1\ 3\ 2\ 2\ 3\ 1\ 3\ 2\ 1
$$
이를 세 개씩 나누어보면,
$$
1\ 3\ 2\ |\ 2\ 3\ 1\ |\ 3\ 2\ 1
$$
로 나눌 수 있는데, 각 부분에서 $1, 2, 3$ 중 어느 숫자라도 고를 수 있음을 알 수 있다.
이를 정리하면 원본 수열에서 $1, 2, 3$을 모두 포함하는 구간이 세 개 존재하면 $1, 2, 3$을 원소로 갖는 길이가 $3$인 모든 수열을 원본 수열의 부분 수열로 갖는다고 할 수 있다.
만약 원본 수열이,
$$
1\ 3\ 2\ 2\ 3\ 1\ 3\ 2
$$
와 같다면 이를 세 구간으로 나누었을 때,
$$
1\ 3\ 2\ |\ 2\ 3\ 1\ |\ 3\ 2
$$
가 되고 $x\ y\ 1$ 꼴의 부분 수열은 존재할 수 없다.
이는 마지막 $1$을 고를 구간이 원본 수열에 존재하지 않기 때문이다.
즉, $1, 2, 3$을 원소로 갖는 길이가 $3$인 모든 수열을 부분 수열로 가지려면 원본 수열은 $[1, 3]$의 수가 모두 존재하는 구간이 적어도 $3$개 있어야 한다.
따라서, $1$부터 $k$까지의 수를 원소로 갖는 길이가 $x$인 모든 수열을 부분 수열로 가지려면 원본 수열은 $[1, k]$의 수가 모두 존재하는 구간이 적어도 $x$개 있어야 한다.
이를 다르게 말하면 $[1, k]$의 수가 모두 존재하는 구간이 $x$개인 원본 수열에서 만들 수 없는 부분 수열의 최소 길이는 $x + 1$이다.
구현#
require "set"
n, k = gets.split.map(&:to_i)
xs = n.times.map { gets.to_i }
count = 0
lookup = Set.new
all = (1..k).to_set
xs.each do |x|
lookup.add x
if lookup == all
count += 1
lookup = Set.new
end
end
puts count + 1
1부터 k까지의 수가 존재하는 구간을 살펴보기 위해 원본 배열을 순회하며 그러한 구간의 개수를 세준다.
이를 위해 집합을 사용했다.
입력으로 들어오는 배열을 순회하며 1부터 k까지의 수가 모두 존재함을 확인하면 구간의 개수를 증가하고 집합을 초기화해준다.
배열을 모두 순회했을 때 구한 count가 1부터 k까지의 수가 모두 존재하는 구간의 개수이므로 count + 1이 문제에서 요구하는 답이다.