Paint By Numbers timer 4초 memory 512MB

Paint By Numbers는 유명한 퍼즐게임으로 이 문제에서는 단순한 1차원 버전의 퍼즐을 고려한다.

우선, 플레이어에게는 개의 칸을 가진 한 행이 주어진다.

각 칸에는 왼쪽부터 오른쪽으로 0번부터 n-1까지 번호가 매겨져 있다.

플레이어는 각 칸을 검정색이나 흰색으로 칠해야 한다.

우리는 검정색 칸을 ‘X’로, 흰색 칸을 ‘_’로 표현한다.

플레이어에게는 추가로 단서들이 주어지는데, 이는 k개의 양의 정수로 구성된 수열 c = [c_​0, ... , c_​k-1]이다.

플레이어는 다음과 같은 방식으로 칸들을 색칠해야 한다: 검정색 칸들이 정확히 k개의 블록을 이루며, 이때 각 블록은 연속된 칸들로 구성된다.

또한, 왼쪽부터 (0번째부터 시작해서) i번째 블록의 검정색 칸의 개수는 c_i와 같다.

예를 들어, 만약 단서들이 c = [3, 4]라면, 퍼즐의 해에는 연속된 검정색 칸들로 구성된 블록이 정확히 두 개 있어야 한다: 한 블록은 길이가 3이고 다른 블록은 길이가 4이다.

따라서, 만약 n = 10이고 c = [3, 4]라면, 단서들을 만족하는 해 중 한가지는 “_XXX__XXXX”이다.

참고로, “XXXX_XXX__”는 검정색 칸들의 블록들의 순서가 바르지 않으므로 단서들을 만족하지 않는다.

또한, “__XXXXXXX_”도 두 개의 구분된 검정색 칸들의 블록이 아니라 단 하나의 블록만 있으므로 단서들을 만족하지 않는다.

여러분에게는 일부분이 풀린 퍼즐의 해가 주어진다.

즉, 여러분은 n과 c를 알며, 추가로 검정색으로 칠해진 일부 칸들과 흰색으로 칠해진 일부 칸들도 안다.

여러분의 작업은 칸들에 대한 추가적인 정보를 추론하는 것이다.

구체적으로, 유효한 해는 단서들을 만족하고 또한 색깔이 알려진 칸들을 만족하는 해이다.

여러분의 프로그램은 모든 유효한 해들에서 항상 검정색으로 칠해져야만 하는 칸들을 찾아야 하고, 모든 유효한 해들에서 항상 흰색으로 칠해져야만 하는 칸들을 찾아야 한다.

유효한 해가 적어도 하나는 존재하는 입력이 주어진다고 가정한다.​